这就是国家集训队嘛i了i了。
关于路径的统计。
考虑对所有路径都对3取模。
然后路径数就是关键了。
设长度为0的路径为n0，长度为1的路径为n1，长度为2的路径为n2
那么1和2组合肯定可以为0。因为反转也算不同的路径，所以要*2。
所以方案数为n1*n2*2；
这里的难点在于与长度为0路径的计算。
我们统计的时候，以每个点为起点和终点来看。
那么终点和起点都有n0种选择，到自己就看成不和其他边组合的方案。
那么就是n0*n0。然后点分治和容斥去统计即可
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2e4+5; const int M = 12005; const LL Mod = 2008; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,cnt = 0,mx = INF,rt,sz,tot = 0; int head[N],ssize[N],vis[N],dis[N]; LL ans = 0; struct Node{int to,dis,next;}e[N<<1]; inline void add(int u,int v,int w) { e[++cnt].to = v,e[cnt].dis = w,e[cnt].next = head[u],head[u] = cnt; } void Findroot(int u,int fa) { ssize[u] = 1;int son = 0; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to; if(v == fa || vis[v]) continue; Findroot(v,u); ssize[u] += ssize[v]; son = max(son,ssize[v]); } son = max(son,sz-ssize[u]); if(son < mx) mx = son,rt = u; } void Dis_slove(int u,int fa,int z) { dis[++tot] = z%3; for(rg int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(v == fa || vis[v]) continue; Dis_slove(v,u,z+d); } } LL slove(int u,int val) { tot = 0; Dis_slove(u,0,val); int num0 = 0,num1 = 0,num2 = 0; for(rg int i = 1;i <= tot;++i) { if(dis[i] == 0) num0++; if(dis[i] == 1) num1++; if(dis[i] == 2) num2++; } LL sum = 0; sum += 1LL*num0*num0+1LL*num1*num2*2; return sum; } void divide(int u) { ans += slove(u,0); dbg(ans); vis[u] = 1; for(int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(vis[v]) continue; ans -= slove(v,d); mx = INF,sz = ssize[v]; Findroot(v,0); divide(rt); } } int main() { n = read(); for(rg int i = 1;i < n;++i) { int x,y,z;x = read(),y = read(),z = read(); add(x,y,z%3);add(y,x,z%3); } mx = INF,sz = n; Findroot(1,0); divide(rt); dbg(ans); LL ma = 1LL*n*n; LL gcd = __gcd(ma,ans); ans /= gcd,ma /= gcd; printf("%lld/%lld ",ans,ma); system("pause"); }
因为模数只有3种可能，所以也可以树形dp统计下面的长度为0,1,2的数量。
然后边转移边统计。用当前子树去更新前面子树。
一开始给与每个点dp[u][0]为1.这样就可以统计不通过父节点的路径方案数。
然后注意模数问题即可，因为我们这样最后是没有统计到到自己的方案的，所以最后加上即可
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2e4+5; const int M = 12005; const LL Mod = 2008; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,cnt = 0; int head[N],dp[N][3]; LL ans = 0; struct Node{int to,dis,next;}e[N<<1]; inline void add(int u,int v,int w) { e[++cnt].to = v,e[cnt].dis = w,e[cnt].next = head[u],head[u] = cnt; } void dfs(int u,int fa) { dp[u][0] = 1; for(int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(v == fa) continue; dfs(v,u); for(rg int j = 0;j < 3;++j) ans += 1LL*dp[v][j]*dp[u][(((3-j-d)%3)+3)%3]*2; for(rg int j = 0;j < 3;++j) dp[u][(j+d)%3] += dp[v][j]; } } int main() { n = read(); for(rg int i = 1;i < n;++i) { int x,y,z;x = read(),y = read(),z = read(); add(x,y,z%3);add(y,x,z%3); } dfs(1,0); ans += n; LL ma = 1LL*n*n; printf("%lld/%lld ",ans/__gcd(ma,ans),ma/__gcd(ma,ans)); system("pause"); }