fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sz(x) (int)x.size()
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ll long long
  7. #define lli long long
  8. #define mod 1000000007
  9. #define mod2 998244353
  10. #define si size()
  11. #define dou double
  12.  
  13. void fast(){
  14. ios_base::sync_with_stdio(false);
  15. cin.tie(NULL);
  16. }
  17.  
  18. void init_code(){
  19. #ifndef ONLINE_JUDGE
  20. freopen("input.txt", "r", stdin);
  21. freopen("output.txt", "w", stdout);
  22. #endif
  23. }
  24.  
  25. long long binpow(long long a, long long b, long long m) {
  26. a %= m;
  27. long long res = 1;
  28. while (b > 0) {
  29. if (b & 1)
  30. res = res * a % m;
  31. a = a * a % m;
  32. b >>= 1;
  33. }
  34. return res;
  35. }
  36. const int mx=1e5+5;
  37. ll int color[mx];
  38. map<pair<ll int,ll int>,ll int> dp;
  39. vector<int> adj[mx];
  40. ll int in[mx];
  41. ll inf=1e11;
  42. long long dfs(ll int node,ll int col,ll int par){
  43. ll ans=0;
  44. if(dp[{node,col}]!=0){
  45. return dp[{node,col}];
  46. }
  47.  
  48.  
  49. for(int next:adj[node]){
  50. if(next!=par){
  51.  
  52. ll minim=inf;
  53. if(color[next]!=-1){
  54. if(color[next]!=col){
  55. minim=min(dfs(next,color[next],node),minim);
  56. }
  57. }else{
  58. for(int i=1;i<=in[next]+1;i++){
  59. if(i!=col){
  60. minim=min(dfs(next,i,node),minim);
  61. }
  62. }
  63. }
  64. ans+=minim;
  65. //cout<<minim<<" "<<next<<"\n";
  66. }
  67.  
  68. }
  69. ans+=col;
  70.  
  71. return dp[{node,col}]=ans;
  72. }
  73.  
  74.  
  75.  
  76. int main(){
  77. fast();
  78. init_code();
  79. int n;
  80. cin>>n;
  81. for(int i=0;i<n-1;i++){
  82. int a,b;
  83. cin>>a>>b;
  84. adj[a].pb(b);
  85. adj[b].pb(a);
  86. in[a]++;
  87. in[b]++;
  88. }
  89. for(ll int i=1;i<=n;i++){
  90. cin>>color[i];
  91. }
  92.  
  93. ll an=inf;
  94. if(color[1]!=-1){
  95. an=min(dfs(1,color[1],-1),an);
  96. }else{
  97. for(int i=1;i<=in[i]+1;i++){
  98. an=min(dfs(1,i,-1),an);
  99. }
  100. }
  101. cout<<an<<"\n";
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114. }
Success #stdin #stdout 0.01s 6004KB
stdin
Standard input is empty
stdout
0