Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<vector>
- #include<algorithm>
- #define MAX_N 3010
- using namespace std;
- int n,k;
- int ans[MAX_N];
- int tmp[MAX_N];
- vector<int> edge[MAX_N];
- vector<int> dp[MAX_N];
- int dfs(int node,int parent)
- {
- dp[node].resize(2);
- dp[node][1] = 0;
- int nsum = 1;
- for(vector<int>::iterator it=edge[node].begin();it!=edge[node].end();it++) if( *it != parent )
- {
- int nchild = dfs( *it , node );
- for(int c=1;c<=nsum+nchild;c++) tmp[c] = MAX_N;
- for(int c=1;c<=nsum;c++) tmp[c] = min( tmp[c] , dp[node][c] + 1 );
- 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] );
- nsum = nsum + nchild;
- dp[node].resize( nsum + 1 );
- for(int c=1;c<=nsum;c++) dp[node][c] = tmp[c];
- }
- return nsum;
- }
- int main()
- {
- for(int c=0;c<MAX_N;c++) ans[c] = MAX_N;
- edge[1].push_back(0);
- scanf("%d",&n);
- for(int c=1;c<n;c++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- edge[x].push_back(y);
- edge[y].push_back(x);
- }
- dfs(1,0);
- for(int c=1;c<=n;c++) for(int d=1;d<dp[c].size();d++)
- {
- if( c == 1 ) ans[d] = min( ans[d] , dp[c][d] );
- else ans[d] = min( ans[d] , dp[c][d] + 1 );
- }
- scanf("%d",&k);
- for(int c=1;c<=k;c++)
- {
- int x;
- scanf("%d",&x);
- if( ans[x] == MAX_N ) printf("-1\n");
- else printf("%d\n",ans[x]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement