BZOJ 3697: 采药人的路径

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

Input

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

Output

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

Sample Input

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

Sample Output

1

HINT

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

Solution

点分治，边权为 $0$ 变成 $-1$，dfs 时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))

int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2];
ll ans;
bool vis[100001];

struct edge
{
    int to,ne,w;
}e[200000];

inline void add(int a,int b,int w)
{
    e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++;
}

void dfs1(int x,int fa)
{
    sz[x]=1;
    for(int i=p[x];i;i=e[i].ne)
        if(!vis[e[i].to]&&e[i].to!=fa)
            dfs1(e[i].to,x),sz[x]+=sz[e[i].to];
}

void dfs2(int x,int fa)
{
    bool ok=sz[ro]<=2*sz[x];
    for(int i=p[x];i;i=e[i].ne)
        if(!vis[e[i].to]&&e[i].to!=fa)
        {
            dfs2(e[i].to,x);
            if(sz[e[i].to]*2>sz[ro])ok=0;
        }
    if(ok)nro=x;
}

void dfs3(int x,int fa,int len)
{
    if(len)
    {
        if(apr[len+n])
            ans+=cnt[n-len][0];
        else
            ans+=cnt[n-len][1];
    }
    else
    {
        if(apr[len+n])
            ans+=cnt[n][0]+1;
        else
            ans+=cnt[n][0];
    }
    apr[len+n]++;
    for(int i=p[x];i;i=e[i].ne)
        if(!vis[e[i].to]&&e[i].to!=fa)
            dfs3(e[i].to,x,len+e[i].w);
    apr[len+n]--;
}

void dfs4(int x,int fa,int len)
{
    if(len)
    {
        if(apr[len+n])
            cnt[n+len][0]++,cnt[n+len][1]++;
        else
            cnt[n+len][0]++;
    }
    else
    {
        cnt[n][0]++;
    }
    apr[len+n]++;
    for(int i=p[x];i;i=e[i].ne)
        if(!vis[e[i].to]&&e[i].to!=fa)
            dfs4(e[i].to,x,len+e[i].w);
    apr[len+n]--;
}

void dfs5(int x,int fa,int len)
{
    cnt[n+len][0]=cnt[n+len][1]=0;
    for(int i=p[x];i;i=e[i].ne)
        if(!vis[e[i].to]&&e[i].to!=fa)
            dfs5(e[i].to,x,len+e[i].w);
}

void solve(int x)
{
    dfs1(x,0);
    ro=x;
    dfs2(x,0);
    vis[nro]=1;
    for(int i=p[nro];i;i=e[i].ne)
        if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w);
    dfs5(nro,0,0);
    for(int i=p[nro];i;i=e[i].ne)
        if(!vis[e[i].to])solve(e[i].to);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c?c:-1),add(b,a,c?c:-1);
    }
    solve(1);
    printf("%lld\n",ans);
}

日期： 2016-12-05

标签： BZOJ 点分治

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/96/ 查看。