题解：P2977 [USACO10JAN] Cow Telephones G

· · 题解

现有题解的写法好像都和我不太一样，所以写一篇题解。

首先找一个非叶子节点作为这棵树的根节点，然后考虑后序遍历贪心。

设 s 为节点 u 的来自子树的所有配对请求数，该节点可以组成的配对数 m=\min(\lfloor \frac{s}{2} \rfloor,K)。

如果还有剩余且 m<K，则 u 节点可以再往上多上传一个请求 f=1 ，否则 f=0。

最后的答案就是 ans=\sum_{u\in T} m(u)。

代码：

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
const int N=1e5+5;

int n,k,fa[N],fwd[N];
vector<int> order;
vector<int> G[N];

void solve(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        G[u].push_back(v),G[v].push_back(u);
    }
    int rt=1;
    for(int i=1;i<=n;i++) if(G[i].size()>1) {
        rt=i; break;
    }
    memset(fa,-1,sizeof(fa));
    stack<int> stk;
    stk.push(rt),fa[rt]=0;
    while(!stk.empty()){
        int u=stk.top(); stk.pop();
        order.push_back(u);
        for(auto v:G[u]) if(fa[v]==-1) fa[v]=u,stk.push(v);
    }
    reverse(order.begin(),order.end());
    ll ans=0;
    for(auto u:order){
        int s=0;
        for(auto v:G[u]) if(v!=fa[u]) s+=fwd[v];
        if(u!=rt&&(int)G[u].size()==1) s++;
        int m=min(s/2,k),f=0;
        if(s-2*m>=1&&m<k) f=1;
        ans+=m,fwd[u]=f;
    }
    return cout<<ans<<"\n",void();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T=1;
    while(T--){
        solve();
    }

    return 0;
}