1 条题解
-
0
#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
- 上传者