简要题意
给你一个 \(n\) 各节点的树，每一个边有一个权值。你需要求出树上任意两个的点之间的简单路径权值和（相同的点结果是 \(0\)）是 \(3\) 的倍数的概率。输出概率的最简分数形式。
\(1 \le n \le 2 \times 10^{4}\)
思路
据说这道题是点分治？可是我不会。
看到了 最高赞题解 后，略有想法，随即关闭题解AC本题。
这道题实际上是可以树上DP的。
定义 \(\sigma(u,v)\) 为 \(u\to v\) 的简单路径权值和。则可以定义 \(f_{u,d}\) 为：
\[f_{u,d} = \sum_{i=1}^{n}{[\sigma(u,i)\bmod 3 = d]}\ (1 \le u \le n,d \in \{0,1,2\}) \]由于 \(\forall u,\sigma(u,u)=0\)，可得初始条件 \(\forall u,f_{u,0}=1\)。
从子节点转移到父节点也是非常的简单，就是累加答案的过程。
如果存在边 \((u,v,w)\) 则：
\[\begin{align} & f_{u,(w+0)\bmod 3} = f_{u,(w+0)\bmod 3}+f_{v,0} \\ & f_{u,(w+1)\bmod 3} = f_{u,(w+0)\bmod 3}+f_{v,1} \\ & f_{u,(w+2)\bmod 3} = f_{u,(w+0)\bmod 3}+f_{v,2} \\ \end{align} \]统计答案比较玄学，但是也没有那篇题解说的那么难，如果一个边 \((x,y,z)\) ，使得存在 \(3\) 的倍数简单路径权值和，转移一定是 \(y\) 的方案加上和 \(x\) 并到一起是 \(3\) 的倍数的方案。我们枚举 \(f_{x,d}\) 中的 \(d\)，则：
\[\operatorname{Ret} = \operatorname{Ret} + 2f_{x,d}f_{y,(3-d-z)\bmod 3} \]至于为什么要乘上 \(2\)，是因为点对具有顺序性。
最终答案显然易见，是 \(\dfrac{\operatorname{Ret}}{n^{2}}\)，记得化简。
时间复杂度 \(O(n)\)
代码
没有过分卡常，速度 \(45\operatorname{ms}\) 目前排在最优解第 \(4\) 页。
#include <bits/stdc++.h>
#define m(x) (((x)%3+3)%3)
#define int long long
using namespace std;
const int N = 2e4+5;
int f[N][5];
struct edge{
int nxt,to,w;
} g[N];
int head[N],ec;
void add(int u,int v,int w){
g[++ec].nxt=head[u];
g[ec].to=v;
g[ec].w=w;
head[u]=ec;
}
int n,ans;
void dfs(int u){
f[u][0]=1;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to,w=g[i].w;
dfs(v);
for(int j=0;j<3;j++){
ans+=f[v][j]*f[u][m(3-j-w)]*2;
}
for(int j=0;j<3;j++){
f[u][m(j+w)]+=f[v][j];
}
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
dfs(1);
ans+=n;
int fu=n*n;
int GCD = __gcd(ans,fu);
ans/=GCD;fu/=GCD;
cout<<ans<<'/'<<fu;
}