采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

第1行包含一个整数N。
接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。

输出符合采药人要求的路径数目。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 typedef long long lnt;

 const int N=;

 struct pnt{

     int hd;

     int dis;

     int wgt;

     bool vis;

 }p[N];

 struct ent{

     int twd;

     int lst;

     int vls;

 }e[N<<];

 lnt f[N<<][],g[N<<][];

 int has[N<<];

 int n;

 lnt top;

 int cnt;

 lnt ans;

 int lim;

 int size;

 int root;

 int maxsize;

 void ade(int f,int t,int v)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=p[f].hd;

     e[cnt].vls=v;

     p[f].hd=cnt;

     return ;

 }

 void grc_dfs(int x,int f)

 {

     p[x].wgt=;

     int maxs=-;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(to==f||p[to].vis)

             continue;

         grc_dfs(to,x);

         p[x].wgt+=p[to].wgt;

         if(p[to].wgt>maxs)

             maxs=p[to].wgt;

     }

     if(maxs<size-p[x].wgt)

         maxs=size-p[x].wgt;

     if(maxs<maxsize)

     {

         maxsize=maxs;

         root=x;

     }

     return ;

 }

 void ans_dfs(int x,int fa,int dep)

 {

     lim=std::max(lim,dep);

     if(has[p[x].dis])

         f[p[x].dis][]++;

     else

         f[p[x].dis][]++;

     has[p[x].dis]++;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(to==fa||p[to].vis)

             continue;

         p[to].dis=p[x].dis+e[i].vls;

         ans_dfs(to,x,dep+);

     }

     has[p[x].dis]--;

     return ;

 }

 void bin_dfs(int x)

 {

     int maxd=;

     p[x].vis=true;

     g[n][]=;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].vis)

             continue;

         p[to].dis=n+e[i].vls;

         lim=;

         ans_dfs(to,to,);

         maxd=std::max(maxd,lim);

         ans+=f[n][]*(g[n][]-);

         for(int j=-lim;j<=lim;j++)

             ans+=g[n-j][]*f[n+j][]+g[n-j][]*f[n+j][]+g[n-j][]*f[n+j][];

         for(int j=n-lim;j<=n+lim;j++)

         {

             g[j][]+=f[j][];

             g[j][]+=f[j][];

             f[j][]=f[j][]=;

         }

     }

     for(int i=n-maxd;i<=n+maxd;i++)

         g[i][]=g[i][]=;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].vis)

             continue;

         root=;

         size=p[to].wgt;

         maxsize=0x3f3f3f3f;

         grc_dfs(to,to);

         bin_dfs(root);

     }

     return ;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;i++)

     {

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         c=c*-;

         ade(a,b,c);

         ade(b,a,c);

     }

     root=;

     size=n;

     maxsize=0x3f3f3f3f;

     grc_dfs(,);

     bin_dfs(root);

     printf("%lld\n",ans);

     return ;

 }