Description
Input
Output
Sample Input
1 4 2 3 2 1 2 4 2 2 4
Sample Output
1 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <vector>#include <list>#include <map>#include <set>#include <deque>#include <queue>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>using namespace std;const int maxn = 1E5 + 10;int n,m;int diameter;int p;vector<int> v[maxn];int d[maxn];int vis[maxn];void dfs(int cur, int ct){ int k = 0; int size = v[cur].size(); int tmp; for(int i = 0;i < size;i++) { tmp = v[cur][i]; if( !vis[tmp]) { vis[tmp] = 1; dfs(tmp,ct + 1); k++; } } if(k == 0) { if(diameter < ct) { diameter = ct; p = cur; } }}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int a,b; for(int i = 1; i <= n; i++) v[i].clear(); for(int i = 0;i < n - 1;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } diameter = 0;p = 1; memset(vis,0,sizeof(vis)); vis[1] = 1; dfs(1,1); memset(vis,0,sizeof(vis)); vis[p] = 1; dfs(p,1); int q; for(int i = 0;i < m;i++) { scanf("%d",&q); if(q <= diameter) printf("%d\n",q - 1); else { printf("%d\n", diameter - 1 + (q - diameter)*2); } } } return 0;} |
[2016-01-27][HDU][4607][Park Visit]
原文：http://www.cnblogs.com/qhy285571052/p/5164927.html