ZJT's Blog

大変に気分がいい~

[自选题 #131] Another Path

2017-12-25 11:542017-12-25 11:54
集训队作业自选题最短路树树链剖分

传送门

我们建出最短路树,考虑点$i$的答案,一定是$i$走到子树内的某个点后,通过一条非树边走出$i$的子树,然后再一路走到根。考虑一条非树边,它只会影响两个点到lca之间路径上的点。所以树剖一下,然后随便维护一些最值就做完了。

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 200010
#define LL long long
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,sizew;
int e2[MAXN][3];
int g[MAXN],nume;
int dep[MAXN],pre[MAXN],prei[MAXN],size[MAXN],son[MAXN],top[MAXN],w[MAXN],numw;
LL d[MAXN];
LL a[MAXN<<2];

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void SPFA(){
    static queue<int> Q;
    static bool inque[MAXN];
    memset(d,0x11,sizeof d);
    Q.push(1);
    d[1]=0;
    inque[1]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        inque[x]=0;
        for(int i=g[x];~i;i=e[i].next)
            if(d[x]+e[i].w<d[e[i].to]){
                d[e[i].to]=d[x]+e[i].w;
                pre[e[i].to]=x;
                prei[e[i].to]=i/2+1;
                if(!inque[e[i].to]){
                    inque[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
    }
}

void dfs(int x){
    size[x]=1;
    son[x]=0;
    for(int i=g[x];~i;i=e[i].next){
        dep[e[i].to]=dep[x]+1;
        dfs(e[i].to);
        size[x]+=size[e[i].to];
        if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
    }
}

void dfs2(int x){
    w[x]=++numw;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x]);
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^son[x]){
            top[e[i].to]=e[i].to;
            dfs2(e[i].to);
        }
}

int getLCA(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
        x=pre[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

void setMax(int x,int cl,int cr,int l,int r,LL v){
    if(l<=cl && cr<=r){
        if(v<a[x]) a[x]=v;
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) setMax(x<<1,cl,mid,l,r,v);
    if(r>mid) setMax(x<<1|1,mid+1,cr,l,r,v);
}

LL query(int x){
    LL res=a[0];
    for(int i=sizew+x-1;i;i>>=1)
        if(a[i]<res) res=a[i];
    return res;
}

void gao(int x,int y,LL v){
    while(top[x]^top[y]){
        setMax(1,1,sizew,w[top[x]],w[x],v);
        x=pre[top[x]];
    }
    if(x^y) setMax(1,1,sizew,w[y]+1,w[x],v);
}

int main(){
#ifdef DEBUG
    freopen("131.in","r",stdin);
#endif
    memset(a,0x77,sizeof a);
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
        e2[i][0]=u;
        e2[i][1]=v;
        e2[i][2]=w;
    }
    SPFA();
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=2;i<=n;i++) addEdge(pre[i],i,d[i]-d[pre[i]]);
    dfs(1);
    top[1]=1;
    dfs2(1);
    for(int i=1;i<=m;i++){
        int u=e2[i][0],v=e2[i][1];
        if(prei[u]==i || prei[v]==i) continue;
        int lca=getLCA(u,v);
        gao(u,lca,d[v]+d[u]+e2[i][2]);
        gao(v,lca,d[v]+d[u]+e2[i][2]);
    }
    for(int i=2;i<=n;i++){
        LL res=query(w[i])-d[i];
        if(res+d[i]==a[0]) res=-1;
        printf("%lld\n",res);
    }
    return 0;
}

查看详细内容

集训队作业之AGC014-E

2017-9-24 13:482017-12-25 11:55
集训队作业AtCoder树套树树链剖分

传送门

其实就是要找一个删边的顺序,使得每次删边之后两边联通块之间只有一条目标的边连着。这里每条目标边可以看成原树上的一条路径。那就直接树剖建线段树,然后对所有目标边在两个端点之间的路径上每条边+1就行了。每次要删边的时候,就找一条当前为1的边,如果找不到就无解,否则就把这条边删了,并且把贡献出这个1的目标边在原树上的路径每条边-1。可以证明这样做一定是对的。(大概就是每条目标边的路径里面最多只会同时存在一条边是1,然后路径里没有共同边的目标边不会互相影响)

考虑怎么找到贡献这个1的目标边。我没想到1个log的做法,直接暴力树套树做的。不知道正解是不是1个log做,也懒得看题解了。。。(然而如果1个log的话就要写lct了)

写的时候全程失智,有一堆细节没考虑(其实也不是细节,都是很明显的地方,只是我比较傻逼),导致调了很久。

代码:

#include <cstdio>
#include <cstring>
#include <cassert>
#include <set>
#include <algorithm>
#define MAXN 200010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,sizew;
int g[MAXN],nume;
int size[MAXN],son[MAXN],dep[MAXN],pre[MAXN],top[MAXN];
int w[MAXN][2],numw,pt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    size[x]=1; son[x]=0;
    pre[x]=p;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dep[e[i].to]=dep[x]+1;
            dfs(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
        }
}

void dfs2(int x,int p){
    pt[w[x][0]=++numw]=x;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x],x);
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && e[i].to!=son[x]){
            top[e[i].to]=e[i].to;
            dfs2(e[i].to,x);
        }
    w[x][1]=numw;
}

namespace Gao1{
    struct node{
        int tag,minv;
    }a[MAXN<<2];

    void pushdown(int x){
        if(a[x].tag){
            a[x<<1].tag+=a[x].tag;
            a[x<<1].minv+=a[x].tag;
            a[x<<1|1].tag+=a[x].tag;
            a[x<<1|1].minv+=a[x].tag;
            a[x].tag=0;
        }
    }

    void add(int x,int l,int r,int cl,int cr,int v){
        if(l<=cl && cr<=r){
            a[x].tag+=v;
            a[x].minv+=v;
            return;
        }
        pushdown(x);
        int mid=(cl+cr)>>1;
        if(l<=mid) add(x<<1,l,r,cl,mid,v);
        if(r>mid) add(x<<1|1,l,r,mid+1,cr,v);
        a[x].minv=min(a[x<<1].minv,a[x<<1|1].minv);
    }

    int find(int x,int cl,int cr){
        if(cl==cr) return cl;
        int mid=(cl+cr)>>1;
        pushdown(x);
        if(a[x<<1].minv==1) return find(x<<1,cl,mid);
        else return find(x<<1|1,mid+1,cr);
    }

    void init(){
        for(int i=1;i<=sizew;i++)
            if(i>=2 && i<=n) a[sizew+i-1].minv=0;
            else a[sizew+i-1].minv=2;
        for(int i=sizew-1;i;i--)
            a[i].minv=min(a[i<<1].minv,a[i<<1|1].minv);
    }

    void add(int x,int y,int v){
        while(top[x]^top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            add(1,w[top[x]][0],w[x][0],1,sizew,v);
            x=pre[top[x]];
        }
        if(x^y) add(1,min(w[x][0],w[y][0])+1,max(w[x][0],w[y][0]),1,sizew,v);
    }

    int find(){
        if(a[1].minv!=1) return -1;
        return pt[find(1,1,sizew)];
    }
}

namespace Gao2{
    multiset< pair<int,int> > S[MAXN<<2];

    void insert(int x,int y){
        for(int i=(sizew+x-1);i;i>>=1) S[i].insert(make_pair(y,x));
        for(int i=(sizew+y-1);i;i>>=1) S[i].insert(make_pair(x,y));
    }

    void remove(int x,int y){
        for(int i=(sizew+x-1);i;i>>=1) S[i].erase(S[i].find(make_pair(y,x)));
        for(int i=(sizew+y-1);i;i>>=1) S[i].erase(S[i].find(make_pair(x,y)));
    }

    pair<int,int> find(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r){
            multiset< pair<int,int> >::iterator it1=S[x].lower_bound(make_pair(l,0)),it2=S[x].lower_bound(make_pair(r+1,0));
            if(it1!=S[x].begin()) return *(--it1);
            if(it2!=S[x].end()) return *it2;
            return make_pair(-1,0);
        }
        int mid=(cl+cr)>>1;
        if(r<=mid) return find(x<<1,l,r,cl,mid);
        if(l>mid) return find(x<<1|1,l,r,mid+1,cr);
        pair<int,int> temp=find(x<<1,l,r,cl,mid);
        if(temp.first!=-1) return temp;
        else return find(x<<1|1,l,r,mid+1,cr);
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    n=read();
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
    dep[1]=1;
    dfs(1,0);
    top[1]=1;
    dfs2(1,0);
    Gao1::init();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        Gao1::add(u,v,1);
        Gao2::insert(w[u][0],w[v][0]);
    }
    for(int i=1;i<n;i++){
        int x=Gao1::find();
        if(x==-1){
            puts("NO");
            return 0;
        }
        pair<int,int> temp=Gao2::find(1,w[x][0],w[x][1],1,sizew);
        assert(temp.first!=-1);
        Gao1::add(pt[temp.first],pt[temp.second],-1);
        Gao1::add(1,w[x][0],w[x][0],1,sizew,2);
        Gao2::remove(temp.first,temp.second);
    }
    puts("YES");
    return 0;
}

查看详细内容