HDU 4607 Park visit (求树的直径)
HDU 直径
2023-09-11 14:14:43 时间
解题思路:
通过两次DFS求树的直径,第一次以随意点作为起点,找到距离该点距离最远的点,则能够证明这个点一定在树的直径上,然后以该点为起点进行DFS得到的最长路就是树的直径。
最后的询问,假设K <= D + 1则能够沿着直径走,距离为K - 1, 假设K >= D + 1。则须要走直径旁边的分支,每訪问一个点距离为2(从直径到这个点,再返回到直径上)。
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <queue> #define LL long long using namespace std; const int MAXN = 100000 + 10; struct Edge { int to, next; }edge[2 * MAXN]; int tot; int head[MAXN]; int dis[MAXN]; int N, M; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int dfs(int u, int pre = -1) { int ans = u; for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].to; if(v == pre) continue; dis[v] = dis[u] + 1; int dv = dfs(v, u); if(dis[ans] < dis[dv]) ans = dv; } return ans; } int solve(int u) { dis[u] = 0; u = dfs(u); dis[u] = 0; return dis[dfs(u)]; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &N, &M); init(); int u, v; for(int i=1;i<N;i++) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } int D = solve(1); for(int i=1;i<=M;i++) { int K; scanf("%d", &K); if(K <= D + 1) cout << K - 1 << endl; else cout << D + (K - D - 1) * 2 << endl; } } return 0; }
相关文章
- hdu 1086 You can Solve a Geometry Problem too 求n条直线交点的个数
- hdu 1277 全文检索 (字典树应用)
- hdu 3308 线段树,单点更新 求最长连续上升序列长度
- HDU 1006 Tick and Tick 时钟指针问题
- HDU 1069 Monkey and Banana(动态规划)
- 【hdu 4315】Climbing the Hill
- 【hdu 1527】取石子游戏
- 【hdu 2108】Shape of HDU
- hdu 3342 Legal or Not (拓扑排序)
- HDU 1973
- hdu 3549 Flow Problem(最大流模板题)
- HDU 1395 2^x mod n = 1
- hdu 4445 Crazy Tank (暴力枚举)
- HDU更多的学校比赛9场 HDU 4965Fast Matrix Calculation【矩阵运算+数学技巧】
- Saving HDU hdu
- HDU 4915 Parenthese sequence