P5258 [JSOI2013]旅行时的困惑

Thunder_S · 2021-10-05 11:23:28 · 题解

不一样的阅读体验

Solution

可以证明，如果一条公交线路可以在子树内建成，就不会在往子树外走。

简单的证明：如果当前子树内有可以连的线路，如果往外走，要么与当前连边数一致，要么多连，答案不会更优。

因此考虑贪心。设 a_i 和 b_i 表示父亲要走过来多少和要往父亲走多少。

对于当前节点 x，它的子节点 son 只有 a_i 和 b_i 中的一个可以传递到 x，那么另一个就可以记录答案。

另外，对于节点 x，优先让其在内部建线路，剩余的再传递上去。

Code

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
struct ndoe
{
    int to,next,head,fx;
}tree[N<<1];
int n,x,y,ans,tot,a[N],b[N];
void add(int x,int y,int opt)
{
    tree[++tot].to=y;
    tree[tot].fx=opt;
    tree[tot].next=tree[x].head;
    tree[x].head=tot;
}
void dfs(int x,int fa)
{
    for (int i=tree[x].head;i;i=tree[i].next)
    {
        int v=tree[i].to;
        if (v==fa) continue;
        dfs(v,x);
        if (tree[i].fx)//看能传递哪一部分，另外一部分计入答案
        {
            ans+=a[v];
            b[x]+=max(b[v],1);
        }
        else
        {
            ans+=b[v];
            a[x]+=max(a[v],1);
        }
    }
    int t=min(a[x],b[x]);
    a[x]-=t;b[x]-=t;ans+=t;//优先在内部连边
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x+1,y+1,1);add(y+1,x+1,0);
    }
    dfs(1,0);
    printf("%d\n",ans+max(a[1],b[1]));
    return 0;
}