BZOJ3697采药人的路径——点分治

题目描述

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

输入

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

输出

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

样例输入

7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1

样例输出

1

提示

对于100%的数据，N ≤ 100,000。

 

点分治经典题，因为答案符合逆运算，所以采用单步容斥统计答案。因为要求0,1边数相等，所以把0边的边权改为-1，这样只要路径和为0就是满足第一条的路径，又因为要有一个中间点，所以不妨设f[i][0/1]分别表示当前点到当前重心边权和为i且没有/有中间点的方案数；g[i][0/1]分别表示当前点到当前重心边权和为-i且没有/有中间点的方案数。注意这里的中间点表示到当前点路径和为0的点。下面就到了这道题的两个难点：1、当前重心到某个子节点路径和为0的答案数要单独统计，不能容斥(但其实好像是可以的，只是很麻烦没必要qwq)，因为端点不能作为中间点。因此对于每个重心要单独统计(dfs一下就行了)，但要在每条路径上第二个到重心路径和为0的点再计入答案(要将第一个点当中间点)。2、如何判断一个点到重心之间是否有中间点是本道题的重中之重。可以用一段区间l,r来表示从当前点到重心的路径上所有点到重心路径和的最大值和最小值，因为每条边都是±1，所以这个区间一定是连续的(即区间中所有路径和都是存在的)，那么当遍历到一个点时如果这个点到重心的路径和在这段区间中就说明有中间点。解释一下为什么：如果这个路径和(设为x)存在过就说明之前路径和为x的这个点到当前点之间路径和为0(怎么样，是不是恍然大悟qwq)。统计之后一步容斥就ok了，但需要注意的是从重心dfs时要把区间初始值赋成1–-1(也就是一段不存在的区间)来防止把重心算进方案数。

最后附上代码(这道题和BZOJ3127是同一道题，双倍经验哦)。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ma;
int n,k;
int tot;
int num;
long long ans;
int root;
int x,y,z;
int to[200010];
int mx[100010];
int val[200010];
int head[100010];
int next[200010];
int size[100010];
bool vis[100010];
long long f[100010][2];
long long g[100010][2];
void add(int x,int y,int v)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    val[tot]=v;
    tot++;
    next[tot]=head[y];
    head[y]=tot;
    to[tot]=x;
    val[tot]=v;
}
void getroot(int x,int fa)
{
    size[x]=1;
    mx[x]=0;
    for(int i=head[x];i;i=next[i])
    {
        if(to[i]!=fa&&!vis[to[i]])
        {
            getroot(to[i],x);
            size[x]+=size[to[i]];
            mx[x]=max(mx[x],size[to[i]]);
        }
    }
    mx[x]=max(mx[x],num-size[x]);
    if(!root||mx[x]<mx[root])
    {
        root=x;
    }
}
void dfs(int x,int fa,int dis,int l,int r)
{
    if(dis>=l&&dis<=r)
    {
        if(dis>=0)
        {
            f[dis][1]++;
        }
        else
        {
            g[-dis][1]++;
        }
    }
    else
    {
        if(dis>=0)
        {
            f[dis][0]++;
        }
        else
        {
            g[-dis][0]++;
        }
    }
    l=min(l,dis);
    r=max(r,dis);
    ma=max(ma,max(-l,r));
    for(int i=head[x];i;i=next[i])
    {
        if(to[i]!=fa&&!vis[to[i]])
        {
            dfs(to[i],x,dis+val[i],l,r);
        }
    }
}
void calc(int x,int fa,int dis,int cnt)//统计以从重心到子节点为路径的答案
{
    if(dis==0)
    {
        if(cnt>=2)
        {
            ans++;
        }
        cnt++;
    }
    for(int i=head[x];i;i=next[i])
    {
        if(!vis[to[i]]&&to[i]!=fa)
        {
            calc(to[i],x,dis+val[i],cnt);
        }
    }
}
void partition(int x)
{
    vis[x]=1;
    calc(x,0,0,0);
    ma=0;
    dfs(x,0,0,1,-1);
    ans+=f[0][1]*(f[0][1]-1)/2;
    f[0][0]=f[0][1]=0;
    for(int i=1;i<=ma;i++)
    {
        ans+=f[i][1]*g[i][0]+f[i][0]*g[i][1]+f[i][1]*g[i][1];
        f[i][1]=f[i][0]=g[i][1]=g[i][0]=0;
    }
    for(int i=head[x];i;i=next[i])
    {
        if(!vis[to[i]])
        {
            ma=0;
            dfs(to[i],0,val[i],0,0);
            ans-=f[0][1]*(f[0][1]-1)/2;
            f[0][0]=f[0][1]=0;
            for(int j=0;j<=ma;j++)
            {
                ans-=f[j][1]*g[j][0]+f[j][0]*g[j][1]+f[j][1]*g[j][1];
                f[j][1]=f[j][0]=g[j][1]=g[j][0]=0;
            }
            num=size[to[i]];
            root=0;
            getroot(to[i],0);
            partition(root);
        }
    }
}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z==0)
        {
            z=-1;
        }
        add(x,y,z);
    }
    mx[0]=num=n;
    getroot(1,0);
    partition(root);
    printf("%lld",ans);
}