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 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; struct nodeType{ int dep; vector<int> to; } node[100005]; bool vis[100005]; inline void init_nodes(int n,bool clearljb){ for (int i = 1; i <= n; i++) { node[i].dep = 1; if(clearljb) node[i].to.clear(); } } int bfs(int n,int init,bool meta){ init_nodes(n,false); memset(vis, 0, sizeof(vis)); queue<int> q; q.push(init); int res = 0; int last = 0; while (!q.empty()) { nodeType &now = node[q.front()]; if (now.dep > res) { res = now.dep; last = q.front(); } //cout << now.dep << endl; vis[q.front()] = true; q.pop(); for (int i = 0; i < now.to.size(); i++) { if (vis[now.to[i]]) { continue; } node[now.to[i]].dep = now.dep+1; q.push(now.to[i]); } } if (meta) { return last; } return res; } int main(int argc, char *argv[]) { int casecnt; cin >> casecnt; while (casecnt--) { int n = 0,m = 0; cin >> n >> m; init_nodes(n,true); for (int i = 1; i <= n-1; i++) { int a = 0,b = 0; scanf(" %d %d",&a,&b); node[a].to.push_back(b); node[b].to.push_back(a); } int seed = (rand()%n)+1; int meta = bfs(n,seed,true); int diam = bfs(n, meta,false); for (int i = 1; i <= m; i++) { int k; scanf(" %d",&k); if (k <= diam) { printf("%dn",k-1); }else{ printf("%dn",diam-1+2*(k-diam)); } } } return 0; } |
树的直径就是最长路,求法其实很简单的,就是两遍dfs,第一遍dfs把终点的节点编号输出来,第二次用这个节点当成起点再来一遍,这回输出最高深度,就是直径。
这个直径用法就是,如果需要过的节点数少于直径长度,说明不用拐弯,沿着直径走就ok,如果需要过的节点数大于直径长度,说明要拐弯,拐弯进去还要再出来,相当于走了两遍,所以是直径长度加上二倍多出来的分支长度,调整一下就ok了。