【usaco 2013 open yinyang】阴阳

题目

Farmer John 正在在计划自己的农场漫步。他的农场的结构就像一棵树:农场有N个谷仓(1<= N <=100,000),分别由N-1条路链接。这样,他便可以通过这些谷仓间的道路遍及各个谷仓。Farmer John想要选择一条路线:这条路线的起点和终点分别为农场中两个不同的谷仓,这条路线不能重复经过一条边两次。Farmer John担心这条路径可能会偏长,所以他想在路线上寻找一个休息点(当然这个休息点不能为起点或者终点)。
每条边的两旁都是牛群,要么是Charcolais(白毛),要么是Angus(黑毛)。Farmer John是一个聪明人,所以他想要在他通过小路的同时平衡小路两侧阴阳的力量。他要选择一条路径使得他从起点到休息站,和从休息站到终点这两段路上都满足路两边的Charcolais牛群和Angus牛群总数量相同。
Farmer John好奇他能找到多少条如上所述的平衡的路径。我们认为,当且仅当两条路线的边的集合不同时,这两条路径才被认为是不同的,否则认为是相同的路线。就算路线上有多个有效的“休息站”的位置能使路线平衡,我们也只记为一条路线。
请帮助计算有多少条不同的平衡路线。

分析

这是一道不错的点分治练手题目,不难很容易打。
但不知道为神马,旁边的几个逗逼ly、风筝都是很tm麻烦,细节很多。
真tm搞不懂+_+。
首先把黑白毛两种牛当做该边的边权-1或1,如果有两个点,到他们路径上某个点的距离为0,那么这就是一个合法路径。
对于一个以x为根的子树,经过x的路径\((i,j),其中deep_{i}<=deep_{j}\)有三种:

一、当i和j分别在x的两个不同的儿子为根的子树中

【usaco 2013 open yinyang】阴阳
显然,\(k\)为中间点。
那如何计算这种情况呢?
定义\(dis_{i}\)表示x到i距离,\(d_{i}\)表示在以x为根的子树中的i的祖先是否出现过一个k点,\(dis_{k}=dis_{i}\),如果是,就为\(true\),否则为\(false\)
我们把每个儿子分开做,这样就不用判重了。
再定义\(b_{i}\)表示,在以x为根的子树中,有多少个节点的\(dis\)值为\(i\)\(b1_{i}\)表示,在以x为根的子树中,有多少个节点的\(dis\)值为\(i\),且\(d\)值为\(true\)
接着就可以愉愉快快地求答案了。
每个儿子用两个递归,第一个来求以x为根的子树答案,第二个来求更新\(b\)\(b1\)
当前递归到\(l\)点时,如果\(d_{l}=true\),那么答案加上\(b[-dis_{l}]\),否则答案加上\(b1[-dis_{l}]\)

二、i和x是同一个点

【usaco 2013 open yinyang】阴阳
这是一种特殊情况,
显然,\(dis_{k},dis_{j}=0\),这很容易搞。
事实上,可以加点小特判,跟上一种情况一起处理,不过细节有点多,
想一想就可以解决了。

三、i不在以x为根的子树中

【usaco 2013 open yinyang】阴阳
这种情况是不用出处理的,
因为当处理\(lca(i,j)\)时,路径\((i,j)\)会被处理掉。

//code中并没有用到d数组,可以省去
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
using namespace std;
long long d[200005],n,m,tot,dis[200005],next[200005],last[200005],to[200005],v[200005];
long long size[200005],mx[200005],root,f,ans,tt,N,b[200005],b1[200005],e[200005];
bool bz[200005],t[200005],g[200005];
long long bj(long long x,long long y,long long z)
{
    next[++tot]=last[x];
    last[x]=tot;
    to[tot]=y;
    v[tot]=z;
}
void getroot(long long x,long long fa)
{
    mx[x]=0;
    size[x]=1;
    for(long long i=last[x];i;i=next[i])
    {
        if(to[i]!=fa && bz[to[i]]) 
        {
            getroot(to[i],x);
            size[x]+=size[to[i]];
            mx[x]=max(mx[x],size[to[i]]);
        }
    }
    mx[x]=max(mx[x],f-size[x]);
    if (mx[x]<mx[root]) root=x;
}
long long dg1(long long x,long long fa)
{
    for(long long i=last[x];i;i=next[i])
    {
        long long j=to[i];
        if(j!=fa && bz[j])
        {
            if(t[dis[j]])
            {
                t[dis[j]]=false;
                b[dis[j]]++;
                dg1(j,x);
                t[dis[j]]=true;
            }
            else
            {
                b1[dis[j]]++;
                b[dis[j]]++;
                dg1(j,x);
            }
        }
    }
}
long long dg(long long x,long long fa)
{
    for(long long i=last[x];i;i=next[i])
    {
        long long j=to[i];
        if(j!=fa && bz[j])
        {  
            dis[j]=dis[x]+v[i];
            if(t[dis[j]])
            {
                if(g[dis[j]])
                {
                    g[dis[j]]=false;
                    e[++tt]=dis[j];
                }
                t[dis[j]]=false;
                ans+=b1[2*N-dis[j]];
                dg(j,x);
                t[dis[j]]=true;
            }
            else
            {
                ans+=b[2*N-dis[j]];
                dg(j,x);
            }
        }
    }
}
long long solve(long long x,long long fa)
{
    bz[x]=false;
    b[N]=1;
    tt=0;
    for(long long i=last[x];i;i=next[i])
    {
        long long j=to[i];
        if(!bz[j] || j==fa) continue;
        dis[j]=v[i]+N;
        if(g[dis[j]])
        {
            g[dis[j]]=false;
            e[++tt]=dis[j];
        }
        t[dis[j]]=false;
        ans+=b1[2*N-dis[j]];
        dg(j,x);
        t[N]=false;
        b[dis[j]]++;
        dg1(j,x);
        t[N]=true;
        t[dis[j]]=true;
    }
    for(long long i=1;i<=tt;i++)
    {
        g[e[i]]=true;
        b[e[i]]=0;
        b1[e[i]]=0;
    }
    b[N]=0;
    for(long long i=last[x];i;i=next[i])
    {
        long long j=to[i];
        if(j!=fa && bz[j])
        {
            root=0;
            f=size[j];
            getroot(j,x);
            solve(root,x);
        }
        
    }
    
}
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n-1;i++)
    {
        long long x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if(!z) z--;
        bj(x,y,z);
        bj(y,x,z);
    }
    mx[0]=maxlongint;
    f=n;
    N=n+1;
    memset(t,true,sizeof(t));
    memset(g,true,sizeof(g));
    memset(bz,true,sizeof(bz));
    root=0;
    getroot(1,0);
    ans=0;
    bz[0]=false;
    solve(root,0);
    printf("%lld",ans);
}

相关推荐