BZOJ

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.