2019 icpc西安邀请赛 点分治

https://nanti.jisuanke.com/t/39277

求$\sum{异或和为0的路径,被其他路径包含的次数}$

如果只是求异或和为0的路径数量,其实是裸点分治,但是加上要求之后,就会复杂一些

进行分类讨论,再特殊处理根节点就行

由于信息可以合并,我使用子树合并,跑的很快

#include<bits/stdc  .h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>#define ll long long#define rep(ii,a,b) for(int ii=a;ii<=b;  ii)#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define fi first#define se secondusing namespace std;//headusing namespace __gnu_pbds;const int maxn=1e5 10,maxm=2e6 10;const ll INF=0x3f3f3f3f,mod=1e9 7;int casn,n,m,k;gp_hash_table<ll,int> cnt;namespace graph{  vector<pair<int,ll>>g[maxn];  int all,sz[maxn],root,maxt;  bool vis[maxn];  int dfs_root(int now,int fa){    int cnt=1;    for(auto i:g[now]){      int to=i.fi;      if(to==fa||vis[to])continue;      cnt =dfs_root(to,now);    }    int tmp=max(cnt-1,all-cnt);    if(maxt>tmp) maxt=tmp,root=now;    return sz[now]=cnt;  }//@基础部分@  int pre[maxn],sz0[maxn],ans;  int dfs_fa(int now,int fa,int cnt=1){    for(auto i:g[now]){      int to=i.fi;      if(to!=fa) cnt =dfs_fa(to,pre[to]=now);    }    int tmp=max(cnt-1,n-cnt);    if(maxt>tmp) maxt=tmp,root=now;    return sz[now]=sz0[now]=cnt;  }    int id[maxn],dfn,sz1[maxn];  ll dis[maxn];  void dfs_dis(int now,int fa,ll d){    dis[  dfn]=d,id[dfn]=now;    if(fa==pre[now]) sz1[now]=sz0[now];    else sz1[now]=n-sz0[fa];    for(auto i:g[now]){      int to=i.fi;      if(to==fa||vis[to]) continue;      dfs_dis(to,now,d^i.se);    }   }  void get_ans(int now){    cnt.clear();    int szroot=0;    for(auto i:g[now]){      int to=i.fi;      if(vis[to]) continue;      dfn=0;      if(pre[to]==now) szroot=n-sz0[to];      else szroot=sz0[now];      dfs_dis(to,now,i.se);      rep(i,1,dfn) {        ans =1ll*cnt[dis[i]]*sz1[id[i]]%mod;        if(ans>=mod) ans-=mod;        if(!dis[i]){          ans =1ll*sz1[id[i]]*szroot%mod;          if(ans>=mod) ans-=mod;        }      }      rep(i,1,dfn) {        int x=cnt[dis[i]];        x =sz1[id[i]];        if(x>=mod) x-=mod;        cnt[dis[i]]=x;      }    }  }  void dfs_dv(int now){    vis[now]=1;    get_ans(now);    for(auto i:g[now]){      int to=i.fi;      if(vis[to]) continue;      all=sz[to];maxt=root=n 1;      dfs_root(to,now);dfs_dv(root);    }  }  void solve(int n){    maxt=root=n 1;    dfs_fa(1,0);dfs_dv(root);  }} using namespace graph;int main(){IO;  cin>>n;  rep(i,2,n){    int a=i,b;    ll c;cin>>b>>c;    g[a].emplace_back(b,c);    g[b].emplace_back(a,c);  }  solve(n);  cout<<ans<<endl;  return 0;}

 

来源：https://www.icode9.com/content-4-480801.html