题目链接:https://www.jisuanke.com/contest/2625
#include<bits/stdc++.h> using namespace std; #define debug puts("YES"); #define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++) #define ll long long #define lrt int l,int r,int rt #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define root l,r,rt #define mst(a,b) memset((a),(b),sizeof(a)) #define pii pair<int,int> #define fi first #define se second #define mk(x,y) make_pair(x,y) const int mod=1e9+7; const int maxn=1e5+100; const int ub=1e6; ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;} ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} ll n,x,cnt[maxn]; ll v,dis[maxn]; pair<ll,int> p[maxn]; vector<pair<int,ll> > g[maxn]; void dfs(int u,int pre){ cnt[u]=1; rep(i,0,g[u].size()){ int v=g[u][i].fi; if(v==pre) continue; dis[v]=(dis[u]^g[u][i].se); dfs(v,u); cnt[u]+=cnt[v]; } } ll ans=0; map<ll,int> mp; void dfs2(int u,int pre){ ans=(ans+1LL*cnt[u]*mp[dis[u]]%mod)%mod; rep(i,0,g[u].size()){ int v=g[u][i].fi; if(v==pre) continue; (mp[dis[u]]+=n-cnt[v])%=mod; dfs2(v,u); (mp[dis[u]]+=-n+cnt[v]+mod)%=mod; } (mp[dis[u]]+=cnt[u])%=mod; } int main(){ ios::sync_with_stdio(false); mst(dis,0),mst(cnt,0); cin>>n; rep(i,2,n+1){ cin>>x>>v; g[i].push_back(mk(x,v)); g[x].push_back(mk(i,v)); } dfs(1,0),dfs2(1,0); cout<<ans<<"\n"; return 0; }
