简要题意
给你一个 (n) 各节点的树，每一个边有一个权值。你需要求出树上任意两个的点之间的简单路径权值和（相同的点结果是 (0)）是 (3) 的倍数的概率。输出概率的最简分数形式。
(1 \le n \le 2 \times 10^{4})
据说这道题是点分治？可是我不会。
这道题实际上是可以树上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
#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>n;
for(int i=1;i>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<
Original: https://www.cnblogs.com/zheyuanxie/p/p2634.html
Author: xiezheyuan
Title: P2634 [国家集训队]聪聪可可
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604583/
转载文章受原作者版权保护。转载请注明原作者出处！