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
联系客服