小道士的矫情之路；
点分治，
对于每个子树，处理其内经过根（重心）的路径，然后递归下一层子树；
如何处理经过根的合法路径
合法有两个要求；
把输入的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?）
由于这里细节极多，不好全部言明，故直接看代码：
1 long long get_ans(int root,int w){ 2 int i,j,k,l,kk,ll; 3 long long ans=0; 4 tot=0;if(w)map[zero]=1; 5 dfs_ans(root,w,0);j=tot; 6 sort(hw+1,hw+tot+1,cmp); 7 for(i=1;i<j;i++){ 8 while(hw[i].d+hw[j].d>0&&i<j) 9 j--; 10 if(hw[i].d+hw[j].d==0){ 11 k=l=0;kk=i;ll=j; 12 if(hw[i].d==0){ 13 for(;i<=j;i++){ 14 if(hw[i].can>=2)k++; 15 if(hw[i].can==1)l++; 16 } 17 ans+=(long long)(k+l)*(k+l-1)/2; 18 ans+=(long long)k*(ll-kk+1-l-k); 19 break; 20 } 21 while(1){ 22 if(hw[i].can)k++;i++; 23 if(hw[i].d!=hw[i-1].d)break; 24 } 25 while(1){ 26 if(hw[j].can)l++;j--; 27 if(hw[j].d!=hw[j+1].d)break; 28 } 29 ans+=(long long)k*(ll-j-l)+l*(i-kk-k)+k*l;i--; 30 } 31 } 32 if(w)map[zero]=0; 33 return ans; 34 } 35 void dfs_ans(int now,int sum,int fa){ 36 hw[++tot].d=sum; 37 hw[tot].can=map[zero+sum]; 38 map[zero+sum]++; 39 for(int i=first[now];i;i=e[i].next) 40 if(e[i].to!=fa&&!vis[e[i].to]) 41 dfs_ans(e[i].to,sum+e[i].d,now); 42 map[zero+sum]--; 43 }
由于这个操作是单次O(logn)的，于是我的做法比标解多了一个不大log;
(标解O（nlogn）,本人O(nlog²n),......大约是这样)
之前桶没清干净，拍了好久没发现；
总代码：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int zero=100004; 5 int n,tot; 6 long long ans; 7 struct half_way{ 8 int d,can; 9 }hw[200010]; 10 int map[200010],vis[100010],size[100010],lsize[100010]; 11 struct ss{ 12 int to,next,d; 13 }e[200010]; 14 int first[100010],num; 15 bool cmp(half_way a,half_way b){ 16 return a.d<b.d; 17 } 18 void build(int ,int ,int ); 19 void part_dfs(int ); 20 void dfs_size(int ,int ); 21 int dfs_root(int ,int ,int ); 22 long long get_ans(int ,int ); 23 void dfs_ans(int ,int ,int ); 24 int main() 25 { 26 int i,j,k,l; 27 scanf("%d",&n); 28 for(i=1;i<n;i++){ 29 scanf("%d%d%d",&j,&k,&l); 30 l=l?1:-1; 31 build(j,k,l); 32 build(k,j,l); 33 } 34 part_dfs(1); 35 printf("%lld",ans); 36 return 0; 37 } 38 void build(int f,int t,int wi){ 39 e[++num].next=first[f]; 40 e[num].to=t;e[num].d=wi; 41 first[f]=num; 42 } 43 void part_dfs(int now){ 44 int i,root; 45 dfs_size(now,0); 46 root=dfs_root(now,0,now); 47 ans+=get_ans(root,0); 48 vis[root]=1; 49 for(i=first[root];i;i=e[i].next) 50 if(!vis[e[i].to]){ 51 ans-=get_ans(e[i].to,e[i].d); 52 part_dfs(e[i].to); 53 } 54 } 55 void dfs_size(int now,int fa){ 56 size[now]=1; 57 for(int i=first[now];i;i=e[i].next) 58 if(!vis[e[i].to]&&e[i].to!=fa){ 59 dfs_size(e[i].to,now); 60 size[now]+=size[e[i].to]; 61 } 62 } 63 int dfs_root(int now,int fa,int r){ 64 int i,root=-1,wroot; 65 lsize[now]=size[r]-size[now]; 66 for(i=first[now];i;i=e[i].next) 67 if(!vis[e[i].to]&&e[i].to!=fa){ 68 if(size[e[i].to]>lsize[now]) 69 lsize[now]=size[e[i].to]; 70 wroot=dfs_root(e[i].to,now,r); 71 if(lsize[wroot]<lsize[root]||root==-1) 72 root=wroot; 73 } 74 if(lsize[now]<lsize[root]||root==-1) 75 root=now; 76 return root; 77 } 78 long long get_ans(int root,int w){ 79 int i,j,k,l,kk,ll; 80 long long ans=0; 81 tot=0;if(w)map[zero]=1; 82 dfs_ans(root,w,0);j=tot; 83 sort(hw+1,hw+tot+1,cmp); 84 for(i=1;i<j;i++){ 85 while(hw[i].d+hw[j].d>0&&i<j) 86 j--; 87 if(hw[i].d+hw[j].d==0){ 88 k=l=0;kk=i;ll=j; 89 if(hw[i].d==0){ 90 for(;i<=j;i++){ 91 if(hw[i].can>=2)k++; 92 if(hw[i].can==1)l++; 93 } 94 ans+=(long long)(k+l)*(k+l-1)/2; 95 ans+=(long long)k*(ll-kk+1-l-k); 96 break; 97 } 98 while(1){ 99 if(hw[i].can)k++;i++; 100 if(hw[i].d!=hw[i-1].d)break; 101 } 102 while(1){ 103 if(hw[j].can)l++;j--; 104 if(hw[j].d!=hw[j+1].d)break; 105 } 106 ans+=(long long)k*(ll-j-l)+l*(i-kk-k)+k*l;i--; 107 } 108 } 109 if(w)map[zero]=0; 110 return ans; 111 } 112 void dfs_ans(int now,int sum,int fa){ 113 hw[++tot].d=sum; 114 hw[tot].can=map[zero+sum]; 115 map[zero+sum]++; 116 for(int i=first[now];i;i=e[i].next) 117 if(e[i].to!=fa&&!vis[e[i].to]) 118 dfs_ans(e[i].to,sum+e[i].d,now); 119 map[zero+sum]--; 120 }
从时间复杂度和代码量上都不如标解，唉，也难怪；