题解：P2977 [USACO10JAN] Cow Telephones G

· · 题解

题解：P2977 [USACO10JAN] Cow Telephones G

题意

给出一棵树，每个节点限定一个可通过的最大值 k，每条边最大可通过值为 1，叶子仅通过最短路连接，求最多多少对叶节点可同时连接。

算法

考虑贪心。

分析

最简单的贪心想法就是将可连接的最近的节点两两连接，但是如果涉及到跨子树的情况就不正确了，因此我们转变思路。 首先，容易想到，最优秀的情况是在每个子树中节点恰好两两配对且不超过父亲节点的最大承载量。那么，就可以分出下面两种情况：

分别处理即可。

代码展示

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+10; 
int n,k;
int res[N],val[N];
/*
   res:标记该子树是否有剩余节点未连接   
   val:记录这颗子树对答案的贡献 
*/ 
int ans;
int tot,head[N*2];

struct edge{
    int nex,to;
}e[N*2];

inline void add(int x,int y)//建边 
{
    tot++;
    e[tot].nex=head[x];
    e[tot].to=y;
    head[x]=tot;
}

inline void dfs(int x,int fa)//遍历 
{
    for(int i=head[x];i;i=e[i].nex)
    {
        if(e[i].to!=fa) 
        {
            dfs(e[i].to,x);
            if(res[e[i].to]==1)//子树内有剩余边 
            {
                if(res[x]==1)
                {
                    val[x]++;//可贡献值++ 
                    res[x]=0;
                }
                else if(val[x]!=k) res[x]=1;//有剩余 
            }
        }
    }
    ans+=val[x];
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
        res[x]++;
        res[y]++;
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}