Advertisement
Guest User

Untitled

a guest
Jun 28th, 2013
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include<cstdio>
  2. #include<vector>
  3. #include<algorithm>
  4. #define MAX_N 3010
  5. using namespace std;
  6.  
  7. int n,k;
  8. int ans[MAX_N];
  9. int tmp[MAX_N];
  10.  
  11. vector<int> edge[MAX_N];
  12. vector<int> dp[MAX_N];
  13.  
  14. int dfs(int node,int parent)
  15. {
  16.     dp[node].resize(2);
  17.     dp[node][1] = 0;
  18.    
  19.     int nsum = 1;
  20.    
  21.     for(vector<int>::iterator it=edge[node].begin();it!=edge[node].end();it++) if( *it != parent )
  22.     {
  23.         int nchild = dfs( *it , node );
  24.    
  25.         for(int c=1;c<=nsum+nchild;c++) tmp[c] = MAX_N;
  26.         for(int c=1;c<=nsum;c++) tmp[c] = min( tmp[c] , dp[node][c] + 1 );
  27.         for(int c=1;c<=nsum;c++) for(int d=1;d<=nchild;d++) tmp[c+d] = min( tmp[c+d] , dp[node][c] + dp[*it][d] );
  28.        
  29.         nsum = nsum + nchild;
  30.         dp[node].resize( nsum + 1 );
  31.    
  32.         for(int c=1;c<=nsum;c++) dp[node][c] = tmp[c];
  33.     }
  34.     return nsum;
  35. }
  36.  
  37. int main()
  38. {
  39.     for(int c=0;c<MAX_N;c++) ans[c] = MAX_N;
  40.     edge[1].push_back(0);
  41.    
  42.     scanf("%d",&n);
  43.     for(int c=1;c<n;c++)
  44.     {
  45.         int x,y;
  46.         scanf("%d%d",&x,&y);
  47.         edge[x].push_back(y);
  48.         edge[y].push_back(x);
  49.     }
  50.    
  51.     dfs(1,0);
  52.    
  53.     for(int c=1;c<=n;c++) for(int d=1;d<dp[c].size();d++)
  54.     {
  55.         if( c == 1 ) ans[d] = min( ans[d] , dp[c][d] );
  56.         else ans[d] = min( ans[d] , dp[c][d] + 1 );
  57.     }
  58.     scanf("%d",&k);
  59.     for(int c=1;c<=k;c++)
  60.     {
  61.         int x;
  62.         scanf("%d",&x);
  63.         if( ans[x] == MAX_N ) printf("-1\n");
  64.         else printf("%d\n",ans[x]);
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement