1 条题解

  • 0
    @ 2025-12-12 19:17:59
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    vector<int>G[N];
    int dp[N],a[N],siz[N],b[N];
    int dfs(int x,int f)
    {
    	int sum=b[x];
    	for(int y:G[x])if(y!=f)
    		sum+=dfs(y,x);
    	dp[x]=min(siz[x],sum);sum=max(sum-siz[x],0);if(sum<0)sum=0;
    	return sum;
    }
    int main()
    {
    	int n,lf=0;cin>>n;
    	for(int i=1;i<=n;i++)cin>>a[i];
    	for(int i=1;i<n;i++)
    	{
    		int x,y;cin>>x>>y;
    		G[x].push_back(y);
    		G[y].push_back(x);
    	}
    	for(int i=1;i<=n;i++)if(G[i].size()==1&&i!=1)lf++,b[i]=1;
    	for(int i=1;i<=lf;i++)siz[a[i]]++;
    	dfs(1,0);
    	int ans=0;for(int i=1;i<=n;i++)ans+=dp[i];
    	cout<<ans;
    	return 0;
    }
    • 1

    信息

    ID
    7514
    时间
    2000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    64
    已通过
    19
    上传者