Steven_MengのBlog

传送门

一道非常模板的点分治,核心函数是$Calc()$,返回当前子树中,经过根节点的链有多少条长度是$3$的倍数,实现时,记录$f_0,f_1,f_2$,分别代表有多少条以根节点为端点的链长度$\mod 3=0,1,2$,最后乘法原理相乘即可。

注意容斥原理,要减去两条链共用一条根节点发出的边的情况,如图中红蓝两条链:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define MAXN 20005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct node{
int to,len;
};
vector<node>G[MAXN];
inline void AddEdge(int u,int v,int w){
G[u].push_back(node{v,w});
}
int sz[MAXN],f[MAXN],root;
int vis[MAXN];
//sz是有向的子树的大小,f是无向的子树的最大值,root为重心
void GetRoot(int u,int father,int tot){
sz[u]=1,f[u]=0;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to;
if (v!=father&&!vis[v]){
GetRoot(v,u,tot);
sz[u]+=sz[v];
f[u]=max(f[u],sz[v]);
}
}
f[u]=max(f[u],tot-sz[u]);
if (f[u]<f[root]) root=u;
}
int ha[3];
void GetDep(int u,int father,int dep){
ha[dep]++;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,w=G[u][i].len;
if (v!=father&&!vis[v]){
GetDep(v,u,(dep+w)%3);
}
}
}
inline int Calc(int u,int w){
ha[0]=ha[1]=ha[2]=0;
GetDep(u,0,w);
return ha[1]*ha[2]*2+ha[0]*ha[0];//1和2可以互相交换,所以两种情况
}
inline void NewRoot(int u,int sz){//将root赋值为以u为根节点的子树(大小sz)的重心
root=0;
GetRoot(u,0,sz);
}
int ans;
void dfs(int u){
ans+=Calc(u,0);
vis[u]=true;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,w=G[u][i].len;
if (!vis[v]){
ans-=Calc(v,w);//容斥
NewRoot(v,sz[v]);
dfs(root);
}
}
}

int gcd(int x,int y){
return x%y==0?y:gcd(y,x%y);
}
int main(){
int n=read();
for (register int i=1;i<n;++i){
int u=read(),v=read(),w=read()%3;
AddEdge(u,v,w);
AddEdge(v,u,w);
}
f[0]=n;
NewRoot(1,n);
dfs(root);
int g=gcd(ans,n*n);
printf("%d/%d\n",ans/g,n*n/g);
}

 评论