SPOJ - COT2 离线路径统计

题意:求\(u\)到\(v\)的最短路径的不同权值种类个数

树上莫队试水题，这一篇是上篇的弱化部分，但可测试以下结论的正确性

设\(S(u,v)\):\(u-v\)最短路径所覆盖的点集

\(S(u,v)=S(root,u)⊕S(root,v)⊕lca(u,v)\)

记\(T(u,v)=S(root,u)⊕S(root,v)\)

每次转移我们只考虑\(T\)的部分,\(lca\)单独处理

对于某一次距离为1的转移,如\(u→u'\)

\(T(u,u')=S(root,u)⊕S(root,u')\)

\(T(u',v)=S(root,u')⊕S(root,v)\)

\(T(u',v)=S(root,u)⊕S(root,v)⊕S(root,u)⊕S(root,u')=T(u,v)⊕T(u,u')\)

得出结论\(T(u',v)=T(u,v)⊕T(u,u')\)

#include<bits/stdc++.h>

#define rep(i,j,k) for(register int i=j;i<=k;i++)

#define rrep(i,j,k) for(register int i=j;i>=k;i--)

#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])

#define print(a) printf("%lld",(ll)(a))

#define println(a) printf("%lld\n",(ll)(a))

#define printbk(a) printf("%lld ",(ll)(a))

using namespace std;

const int MAXN = 2e5+11;

const int INF = 0x7fffffff;

typedef long long ll;

ll read(){

    ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int to[MAXN<<1],nxt[MAXN<<1],head[MAXN],tot;

void init(){

    memset(head,-1,sizeof head);

    tot=0;

}

void add(int u,int v){

    to[tot]=v;

    nxt[tot]=head[u];

    head[u]=tot++;

}

int color[MAXN],belong[MAXN],depth[MAXN],dfn[MAXN];

int stk[MAXN],bit[32],limit,root,cnt,CLOCK,top;

int anc[MAXN][20];

map<int,int> haxi;

bool vis[MAXN];

int ANS,cntNum[MAXN],ans[MAXN];

struct QQQ{

    int u,v,id;

    bool operator < (const QQQ &rhs) const{

        if(belong[u]!=belong[rhs.u]){

            return belong[u]<belong[rhs.u];

        }else{

            return dfn[v]<dfn[rhs.v];

        }

    }

}Q[MAXN];

int dfs(int u,int fa,int d){

    dfn[u]=++CLOCK;

    anc[u][0]=fa; depth[u]=d;

    rep(i,1,16){

        if(depth[u]<bit[i]) break;

        anc[u][i]=anc[anc[u][i-1]][i-1];

    }

    int num=0;

    erep(i,u){

        int v=to[i];

        if(v==fa) continue;

        num+=dfs(v,u,d+1);

        if(num>=limit){

            ++cnt;

            rep(i,1,num) belong[stk[top--]]=cnt;

            num=0;

        }

    }

    stk[++top]=u; num++;

    return num;

}

int lca(int u,int v){

    if(depth[u]<depth[v]) swap(u,v);

    int d=depth[u]-depth[v];

    for(int i=0;bit[i]<=d;i++){

        if(d>>i&1) u=anc[u][i];

    }

    for(int i=16;i>=0;i--){

        if(anc[u][i]!=anc[v][i]){

            u=anc[u][i];

            v=anc[v][i];

        }

    }

    if(u==v) return u;

    else return anc[u][0];

}

void rev(int u){

    if(!vis[u]){

        vis[u]=1;

        if(cntNum[color[u]]==0) ANS++;

        cntNum[color[u]]++;

    }else{

        vis[u]=0;

        if(cntNum[color[u]]==1) ANS--;

        cntNum[color[u]]--;

    }

}

void viss(int u,int v){

    while(u!=v){

        if(depth[u]>depth[v]) rev(u),u=anc[u][0];

        else rev(v),v=anc[v][0];

    }

}

int main(){

    int n,m;

    bit[0]=1;rep(i,1,30) bit[i]=bit[i-1]<<1;

    while(cin>>n>>m){

        init(); limit=sqrt(n)+1;

        haxi.clear(); int haxiid=0;

        rep(i,1,n){

            int t=read();

            if(haxi[t]==0) haxi[t]=++haxiid;

            color[i]=haxi[t];

        }

        rep(i,1,n-1){

            int u=read();

            int v=read();

            add(u,v),add(v,u);

        }

        root=1;

        top=cnt=CLOCK=0;

        memset(anc,0,sizeof anc);

        dfs(root,0,1);

        if(top){

            cnt++;

            while(top) belong[stk[top--]]=cnt;

        }

        rep(i,1,m){

            Q[i].u=read();

            Q[i].v=read();

            Q[i].id=i;

        }

        sort(Q+1,Q+1+m); ANS=0;

        int t=lca(Q[1].u,Q[1].v);

        memset(vis,0,sizeof vis);

        viss(Q[1].u,Q[1].v);

        rev(lca(Q[1].u,Q[1].v));

        ans[Q[1].id]=ANS;

        rev(lca(Q[1].u,Q[1].v));

        rep(i,2,m){

            viss(Q[i-1].u,Q[i].u);

            viss(Q[i-1].v,Q[i].v);

            rev(lca(Q[i].u,Q[i].v));

            ans[Q[i].id]=ANS;

            rev(lca(Q[i].u,Q[i].v));

        }

        rep(i,1,m) println(ans[i]);

    }

    return 0;

}

巴特西

SPOJ - COT2 离线路径统计

最新文章

热门文章