小道士的矫情之路；
点分治，
对于每个子树，处理其内经过根（重心）的路径，然后递归下一层子树；
如何处理经过根的合法路径
合法有两个要求；
把输入的0改成-1后
1.len=0;
2.存在一个点i使被她分开的两个路径len均为零；
在每次统计中我们可以dfs统计每条从根开始的路径（half_way），
任意两条这样的路径拼成一条可能合法的路径；
check合法？
通过dfs;
统计1，每个half_way的len
还要统计,2，这个half_way上是否有一个点到half_way的终点（根之外的那个）的len=0;
一，两个half_way的len加为0才可能合法；
二，两个half_way中至少一个满足“有一个点到half_way的终点（根之外的那个）的len=0”;
只要满足一&&二，则路径合法；（自己思考why?）
1很好统计；
关键是2；
可以考虑维护一个桶；
如果root到i的路径len=x，且桶x已经有值了，则i的二合法；（自己思考why?）
由于这里细节极多，不好全部言明，故直接看代码：
long long get_ans(int root,int w){
int i,j,k,l,kk,ll;
long long ans=;
tot=;if(w)map[zero]=;
dfs_ans(root,w,);j=tot;
sort(hw+,hw+tot+,cmp);
for(i=;i<j;i++){
while(hw[i].d+hw[j].d>&&i<j)
j--;
if(hw[i].d+hw[j].d==){
k=l=;kk=i;ll=j;
if(hw[i].d==){
for(;i<=j;i++){
if(hw[i].can>=)k++;
if(hw[i].can==)l++;
}
ans+=(long long)(k+l)*(k+l-)/;
ans+=(long long)k*(ll-kk+-l-k);
break;
}
while(){
if(hw[i].can)k++;i++;
if(hw[i].d!=hw[i-].d)break;
}
while(){
if(hw[j].can)l++;j--;
if(hw[j].d!=hw[j+].d)break;
}
ans+=(long long)k*(ll-j-l)+l*(i-kk-k)+k*l;i--;
}
}
if(w)map[zero]=;
return ans;
}
void dfs_ans(int now,int sum,int fa){
hw[++tot].d=sum;
hw[tot].can=map[zero+sum];
map[zero+sum]++;
for(int i=first[now];i;i=e[i].next)
if(e[i].to!=fa&&!vis[e[i].to])
dfs_ans(e[i].to,sum+e[i].d,now);
map[zero+sum]--;
}
由于这个操作是单次O(logn)的，于是我的做法比标解多了一个不大log;
(标解O（nlogn）,本人O(nlog²n),......大约是这样)
之前桶没清干净，拍了好久没发现；
总代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int zero=;
int n,tot;
long long ans;
struct half_way{
int d,can;
}hw[];
int map[],vis[],size[],lsize[];
struct ss{
int to,next,d;
}e[];
int first[],num;
bool cmp(half_way a,half_way b){
return a.d<b.d;
}
void build(int ,int ,int );
void part_dfs(int );
void dfs_size(int ,int );
int dfs_root(int ,int ,int );
long long get_ans(int ,int );
void dfs_ans(int ,int ,int );
int main()
{
int i,j,k,l;
scanf("%d",&n);
for(i=;i<n;i++){
scanf("%d%d%d",&j,&k,&l);
l=l?:-;
build(j,k,l);
build(k,j,l);
}
part_dfs();
printf("%lld",ans);
return ;
}
void build(int f,int t,int wi){
e[++num].next=first[f];
e[num].to=t;e[num].d=wi;
first[f]=num;
}
void part_dfs(int now){
int i,root;
dfs_size(now,);
root=dfs_root(now,,now);
ans+=get_ans(root,);
vis[root]=;
for(i=first[root];i;i=e[i].next)
if(!vis[e[i].to]){
ans-=get_ans(e[i].to,e[i].d);
part_dfs(e[i].to);
}
}
void dfs_size(int now,int fa){
size[now]=;
for(int i=first[now];i;i=e[i].next)
if(!vis[e[i].to]&&e[i].to!=fa){
dfs_size(e[i].to,now);
size[now]+=size[e[i].to];
}
}
int dfs_root(int now,int fa,int r){
int i,root=-,wroot;
lsize[now]=size[r]-size[now];
for(i=first[now];i;i=e[i].next)
if(!vis[e[i].to]&&e[i].to!=fa){
if(size[e[i].to]>lsize[now])
lsize[now]=size[e[i].to];
wroot=dfs_root(e[i].to,now,r);
if(lsize[wroot]<lsize[root]||root==-)
root=wroot;
}
if(lsize[now]<lsize[root]||root==-)
root=now;
return root;
}
long long get_ans(int root,int w){
int i,j,k,l,kk,ll;
long long ans=;
tot=;if(w)map[zero]=;
dfs_ans(root,w,);j=tot;
sort(hw+,hw+tot+,cmp);
for(i=;i<j;i++){
while(hw[i].d+hw[j].d>&&i<j)
j--;
if(hw[i].d+hw[j].d==){
k=l=;kk=i;ll=j;
if(hw[i].d==){
for(;i<=j;i++){
if(hw[i].can>=)k++;
if(hw[i].can==)l++;
}
ans+=(long long)(k+l)*(k+l-)/;
ans+=(long long)k*(ll-kk+-l-k);
break;
}
while(){
if(hw[i].can)k++;i++;
if(hw[i].d!=hw[i-].d)break;
}
while(){
if(hw[j].can)l++;j--;
if(hw[j].d!=hw[j+].d)break;
}
ans+=(long long)k*(ll-j-l)+l*(i-kk-k)+k*l;i--;
}
}
if(w)map[zero]=;
return ans;
}
void dfs_ans(int now,int sum,int fa){
hw[++tot].d=sum;
hw[tot].can=map[zero+sum];
map[zero+sum]++;
for(int i=first[now];i;i=e[i].next)
if(e[i].to!=fa&&!vis[e[i].to])
dfs_ans(e[i].to,sum+e[i].d,now);
map[zero+sum]--;
}
从时间复杂度和代码量上都不如标解，唉，也难怪；