题解：CF369C Valera and Elections

leixinranYY · 2025-12-01 23:33:28 · 题解

思路

首先，根据题意，每一次修复的道路都是从一个点到根节点 1，然后如何才能使选的人数最小。

然后这道题不难发现：对于一个节点 i，如果与父节点的道路是需要修建的，那么我们接下来看的就是有问题道路的子树。如果没有，那么节点 i 就是答案之一。

为什么是正确的？是因为如果与 i 相连的子树中如果有问题道路，那么选 i 就不是最优的，就需要继续向下看。如果没有问题道路，那么以选第 i 个人就可以解决问题，并且最优。

所以我们先预处理以根节点为 i 的子树有多少条问题道路，然后我们再从根节点开始向下遍历，按照刚才的结论进行判断。

代码

#include <bits/stdc++.h>
using namespace std;
int rd() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||'9'<c) {
        if(c=='-') f=-1;
        c=getchar();
    } while('0'<=c && c<='9') {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    } return x*f;
}
const int N=1e5+10;
struct node { int v,w,id; };
vector <node> a[N];
vector <int> res;
int n,dis[N];
void dfs(int u,int fa,int w) {
    for(auto tp:a[u]) {
        int v=tp.v,w=tp.w;
        if(v==fa) continue;
        dfs(v,u,w);
        dis[u]+=dis[v]+w;
    }
}
void dfs1(int u,int fa) {
    bool p=0;
    if(u!=1 && a[u].size()==1)
        res.push_back(u),p=1;
    int cnt=0;
    for(auto tp:a[u]) {
        int v=tp.v,w=tp.w;
        if(v==fa) continue ;
        if(dis[v]+w==0) cnt++;
        else dfs1(v,u);
    }
    if(u!=1 && cnt==(int)a[u].size()-1 && !p)
        res.push_back(u);
}
int main() {
    n=rd();
    for(int i=1;i<n;i++) {
        int u=rd(),v=rd(),w=rd()-1;
        a[u].push_back({v,w,i});
        a[v].push_back({u,w,i});
    }
    dfs(1,0,0);
    dfs1(1,0);
    cout<<res.size()<<endl;
    for(int v:res) cout<<v<<" ";
    return 0;
}