80分求调
查看原帖
80分求调
1241536
hong__hua__miao楼主2025/7/30 10:10
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e4 + 5;
vector <int> G[maxn];
bool vis[maxn];
int dp[maxn][4];
void dfs(int x) {
    vis[x] = 1;
    bool flag = 0;
	int p = maxn * 10;
    for(int i = 0; i < G[x].size(); ++i)
        if(! vis[G[x][i]]) {
            dfs(G[x][i]);
            dp[x][0] += min(dp[G[x][i]][0],min(dp[G[x][i]][1],dp[G[x][i]][2]));
            dp[x][1] += min(dp[G[x][i]][0],dp[G[x][i]][2]);
            if(dp[G[x][i]][0] <= dp[G[x][i]][2]){
                flag = 1;
                dp[x][2] += dp[G[x][i]][0];
            }
            else {
                p = min(p,dp[G[x][i]][0] - dp[G[x][i]][2]);
                dp[x][2] += dp[G[x][i]][2];
            }
        }
    if(flag == 0)
        dp[x][2] += p;
    dp[x][0] ++;
}
signed main(){
	int n;
	scanf("%lld",&n);
	int x,y;
	for (int i = 1; i < n; ++i){
	scanf("%lld%lld",&x,&y);
	G[x].push_back(y);
	G[y].push_back(x);
}
	dfs(1);
	printf("%lld",min(min(dp[1][1],dp[1][0]),dp[1][2]));
    return 0;
}
2025/7/30 10:10
加载中...