[luogu3359]改造异或树

luogu

和之前某道题类似只有删边的话考虑倒着加边

但是怎么统计答案呢?

我们考虑以任意点为根dfs一遍求出每个点到根的路径异或和s[i]

这样任意两点x,y的路径异或和可以表示成s[x] xor s[y]

那么设当前连的边的边权为w,我们要找出被连通的两个连通块中s[x] xor s[y]=w的(x,y)个数

考虑启发式合并,枚举size小的一边,另一边在map上查,然后把size小的map并到大的中去

#define ll long long

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5;

int re(){

    int x=0,w=1;char ch=getchar();

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

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

    return x*w;

}

int n,cnt;

ll sum,ans[_];

map<int,ll>M[_];

map<int,ll>::iterator it;

int h[_],s[_],fa[_],a[_],b[_],c[_],p[_];

struct edge{int to,next,w;}e[_<<1];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void link(int u,int v,int w){

    e[++cnt]=(edge){v,h[u],w};h[u]=cnt;

    e[++cnt]=(edge){u,h[v],w};h[v]=cnt;

}

void dfs(int u,int fa){

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa)continue;

        s[v]=s[u]^e[i].w;

        dfs(v,u);

    }

}

int main(){

    n=re();

    for(int i=1;i<n;i++){

        a[i]=re(),b[i]=re(),c[i]=re();

        link(a[i],b[i],c[i]);

    }

    for(int i=1;i<n;i++)

        p[i]=re();

    dfs(1,0);

    for(int i=1;i<=n;i++)fa[i]=i,M[i][s[i]]=1;

    for(int i=n-1;i>=1;i--){

        int x=find(a[p[i]]),y=find(b[p[i]]);

        if(M[x].size()<M[y].size())swap(x,y);

        fa[y]=x;

        for(it=M[y].begin();it!=M[y].end();++it)

            sum+=1ll*M[x][(*it).first]*(*it).second;

        for(it=M[y].begin();it!=M[y].end();++it)

            M[x][(*it).first]+=(*it).second;

        ans[i]=sum;

    }

    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);

    return 0;

}

巴特西

[luogu3359]改造异或树

[luogu3359]改造异或树

最新文章

热门文章