一开始又看错题,以为同样路径上不同的休息站是算不同路径,后来发现休息站只是路径合法的条件
毫无疑问是树的分治,下面我们只要考虑计算能建休息站的路径
我们把阳看作路径权值为1,阴作为路径权值-1
点分治之后,休息站的建立只有三种情况,在根,在之前的子树路径上,在现在的子树路径上
我们先考虑休息站在根到子树的路径上,我们设d[x]表示点x到根的路径距离
能建也就是说在x到根的路径上存在一点y,d[y]=d[x],也就是当前距离之前是否出现过,打个标记即可
然后我们只要分别记录一下当前由根出发路径和为x,能否在这条路径上建休息站的路径数目就很容易统计了
注意一些地方的漏算和重复计算

 type node=record
po,next,num:longint;
end; var w,g:array[-..,..] of int64;
s,p,f,d:array[..] of longint;
v:array[..] of boolean;
can:array[-..] of longint;
e:array[..] of node;
l,r,root,len,i,x,tot,y,z,n:longint;
ans:int64; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure add(x,y,z:longint);
begin
inc(len);
e[len].po:=y;
e[len].num:=z;
e[len].next:=p[x];
p[x]:=len;
end; procedure getroot(x,fa:longint);
var i,y:longint;
begin
i:=p[x];
s[x]:=;
f[x]:=;
while i<> do
begin
y:=e[i].po;
if not v[y] and (y<>fa) then
begin
getroot(y,x);
s[x]:=s[x]+s[y];
f[x]:=max(f[x],s[y]);
end;
i:=e[i].next;
end;
f[x]:=max(f[x],tot-s[x]);
if f[x]<f[root] then root:=x;
end; procedure dfs(x,fa:longint);
var i,y:longint;
begin
if can[d[x]]> then
begin
inc(g[d[x],]);
ans:=ans+w[-d[x],]+w[-d[x],];
end
else begin
inc(g[d[x],]);
ans:=ans+w[-d[x],];
end;
inc(can[d[x]]);
r:=max(r,d[x]);
if l>d[x] then l:=d[x];
i:=p[x];
while i<> do
begin
y:=e[i].po;
if not v[y] and (y<>fa) then
begin
d[y]:=d[x]+e[i].num;
dfs(y,x);
end;
i:=e[i].next;
end;
dec(can[d[x]]);
end; procedure work(x:longint);
var i,y,j:longint;
begin
v[x]:=true;
i:=p[x];
l:=; r:=;
w[,]:=; //注意根节点可以作为终点
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
d[y]:=e[i].num;
dfs(y,x);
ans:=ans+(w[,]-)*g[,]; //注意当前子树内不能建休息站且路径和为0可以和之前的子树内(不包括单独根节点)这样的路径组成合法路径(根节点是休息站),而之前的计算我们是没有算进去的
for j:=l to r do
begin
w[j,]:=w[j,]+g[j,]; //更新
w[j,]:=w[j,]+g[j,];
g[j,]:=; g[j,]:=;
end;
end;
i:=e[i].next;
end;
for j:=l to r do
begin
w[j,]:=;
w[j,]:=;
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
root:=;
tot:=s[y];
getroot(y,);
work(root);
end;
i:=e[i].next;
end;
end; begin
readln(n);
for i:= to n- do
begin
readln(x,y,z);
if z= then z:=-;
add(x,y,z);
add(y,x,z);
end;
f[]:=n+;
tot:=n;
len:=;
getroot(,);
work(root);
writeln(ans);
end.
04-18 01:24