题目:Park Visit
题意:一个人去公园,想走K个景点,问最短的距离。
思路:求出树的直径(最长的链、最长路径)。从任意点A,找到离A最远点B。再找到离B最远点C,BC就是最长路径。如果K<BC,那只沿着链走就可以了。否则,就要从链上点走出去,再走回来.
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back #define maxint 0x7fffffff const int maxn = 100010; int t, n, m, k; int M, N, maxd; int from, to; vector <int> G[maxn]; bool vis[maxn]; inline void add_edge(int from, int to){ G[from].push_back(to); G[to].push_back(from); } int dfs(int x, int d){ // cout << x << ' ' << d << endl; int res = d; vis[x] = 1; if( maxd < d) { N = x; maxd = d; } for(int i = 0; i < G[x].size(); i ++){ if( vis[G[x][i]] ) continue; res = max( res, dfs(G[x][i], d+1)); } vis[x] = 0; return res; } int solve(){ maxd = 0; dfs(1, 0); // cout << N << ' ' << maxd << endl; return dfs(N, 0); } int main(){ // cin >> t; scanf("%d",&t); int from, to; while(t --) { memset(vis, 0, sizeof(vis)); for(int i = 0; i < maxn; i ++) G[i].clear(); // cin >> n >> m; scanf("%d%d", &n, &m); for(int i = 0; i < n-1; i ++) { // cin >> from >> to; scanf("%d%d",&from, &to); add_edge(from, to); } // system("pause"); solve(); maxd ++; // cout << "maxlen " << maxlen << endl; for(int i = 0; i < m; i ++) { // cin >> k; scanf("%d",&k); if( k < maxd ) printf("%d\n",k-1); else printf("%d\n",(k-maxd)*2+ maxd-1); } } return 0; }