fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/01Mw2D
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!