BZOJ 2152

传送门

头一次搞点分治…

点分治大概是这个姿势:

  • 找到整棵树的重心,然后按照题目要求搞这个重心周围的子树
  • 对每一棵子树再进行上面这样的操作

一般的点分治似乎还要考虑重复计算的部分,要用容斥原理算重复的情况,但这道题不用…以后写了再说吧…

这道题只用对于每个重心,算出这个重心到它子树中的所有点每条路径权值和$mod\ 3=0,1,2$的个数,然后分情况计算一下

最后将上面那步计算的答案$\times 2+n$(每条路径左右端点调换+单个点的情况)除$n^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
89
90
91
92
93
94
95
96
97
98
99
program bzoj_2152;
var cnt:array[1..20000,0..2]of longint;
v:array[1..20000]of boolean;
lst,size:array[1..20000]of longint;
l:array[1..40000]of record ed,pre,w:longint; end;
n,i,a,b,w,tot,root,max,ans,up,dn,g:longint;
function gcd(a,b:longint):longint;
begin
if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
procedure link(a,b,w:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].w:=w;
end;
procedure find_root(t,fa:longint);
var cnt,k:longint;
begin
cnt:=0;
size[t]:=1;
k:=lst[t];
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then
begin
find_root(l[k].ed,t);
inc(size[t],size[l[k].ed]);
if size[l[k].ed]>cnt then cnt:=size[l[k].ed];
end;
k:=l[k].pre;
end;
if tot-cnt>cnt then cnt:=tot-cnt;
if cnt<max then
begin
max:=cnt;
root:=t;
end;
end;
procedure dfs(t,fa,now,rem:longint);
var k:longint;
begin
inc(cnt[now,rem]);
k:=lst[t];
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then dfs(l[k].ed,t,now,(rem+l[k].w)mod 3);
k:=l[k].pre;
end;
end;
procedure find(rt:longint);
var k:longint;
c:array[0..2]of longint;
begin
v[rt]:=true;
k:=lst[rt];
while k<>0 do
begin
if not v[l[k].ed] then
begin
c:=cnt[rt];
dfs(l[k].ed,rt,rt,l[k].w);
inc(ans,(c[0]+1)*(cnt[rt,0]-c[0])+c[1]*(cnt[rt,2]-c[2])+c[2]*(cnt[rt,1]-c[1]));
tot:=size[l[k].ed];
max:=maxlongint;
find_root(l[k].ed,0);
find(root);
end;
k:=l[k].pre;
end;
end;
begin
readln(n);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b,w);
link(a,b,w mod 3);
link(b,a,w mod 3);
end;
tot:=n;
max:=maxlongint;
fillchar(v,sizeof(v),false);
find_root(1,0);
ans:=0;
find(root);
up:=ans*2+n;
dn:=sqr(n);
g:=gcd(up,dn);
writeln(up div g,'/',dn div g);
end.