不是那么裸的点分治。
$f[i][0/1]$表示当前节点的一个子树中总权值和为$i$，且是否存在一个前缀使得其前缀和为$i$
$g[i][0/1]$表示当前节点的已遍历过的子树，其余一样。
对于每个节点
$ans_{node}=g[0][0]∗f[0][0]+ \sum (g[−i][0]∗f[i][1]+g[−i][1]∗f[i][0]+g[−i][1]∗f[i][1])$
另外，Race那道题选根的方案在这里好像不是很适用，容易出问题，还是换黄学长的比较好。
//BZOJ 3697
//by Cydiater
//2016.9.26
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,sum,root,siz[MAXN],dis[MAXN],pre[MAXN],deep[MAXN];
int maxdeep,max_siz[MAXN];
ll ans=,f[MAXN][],g[MAXN][];
bool vis[MAXN];
struct edge{
int y,next,v;
}e[MAXN];
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
void init(){
N=read();
up(i,,N){
ll x=read(),y=read(),v=read()==?-:;
insert(x,y,v);
insert(y,x,v);
}
}
void make_root(int node,int fa){
max_siz[node]=;siz[node]=;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){
make_root(e[i].y,node);
siz[node]+=siz[e[i].y];
max_siz[node]=max(max_siz[node],siz[e[i].y]);
}
max_siz[node]=max(max_siz[node],sum-max_siz[node]);
if(max_siz[node]<max_siz[root])root=node;
}
void dfs(int node,int father){
]++;
]++;
pre[dis[node]]++;
maxdeep=max(deep[node],maxdeep);
for(int i=LINK[node];i;i=e[i].next)
if(e[i].y!=father&&!vis[e[i].y]){
deep[e[i].y]=deep[node]+;
dis[e[i].y]=dis[node]+e[i].v;
dfs(e[i].y,node);
}
pre[dis[node]]--;
}
void work(int node){
vis[node]=;g[N][]=;;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){
dis[e[i].y]=e[i].v+N;deep[e[i].y]=;maxdeep=;
dfs(e[i].y,);mx=max(mx,maxdeep);
ans+=1LL*(g[N][]-)*f[N][];
up(k,-maxdeep,maxdeep)
ans+=1LL*g[N-k][]*f[N+k][]+1LL*g[N-k][]*f[N+k][]+1LL*g[N-k][]*f[N+k][];
up(j,N-maxdeep,N+maxdeep){
g[j][]+=f[j][];
g[j][]+=f[j][];
f[j][]=f[j][]=;
}
}
up(j,N-mx,N+mx)g[j][]=g[j][]=;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){
root=;sum=siz[e[i].y];
make_root(e[i].y,);
work(root);
}
}
void slove(){
sum=N;root=;max_siz[root]=N;
make_root(,);
work(root);
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
;
}