Description

采药人的药田是一个树状结构，每条路径上都种植着同种药材。

采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。

采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

Solution

一开始是按只有重心才作为休息站写的，写着写着发现并不是这样…后来看了黄学长的代码

好鬼畜的点分治QwQ

先把边权为0的变为-1，这样和为0就意味着阴阳平衡

h[i][1/0]表示之前的子树距离为i，是否存在休息站的路径的数量，g[i][1/0]表示这一子树距离为i，是否存在休息站的路径的数量

存在休息站与否可以用同一距离是否第二次出现来判定（这说明这一段的和一定是0）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define INF 0x3f3f3f3f#define MAXN 100005typedef long long LL;using namespace std;int n,root=0,tot=0,num,maxdeep,t[2*MAXN],siz[MAXN],maxv[MAXN],head[MAXN],cnt=0;LL ans=0,g[MAXN*2][2],h[MAXN*2][2];bool vis[MAXN];struct Node1{    int next,to,w;}Edges[MAXN*2];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}void addedge(int u,int v,int w){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v,Edges[cnt].w=w;}void getroot(int u,int f){    siz[u]=1,maxv[u]=0;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==f||vis[v])continue;        getroot(v,u);        siz[u]+=siz[v],maxv[u]=max(maxv[u],siz[v]);    }    maxv[u]=max(maxv[u],tot-siz[u]);    if(maxv[u]