【AcWing325】计算机
标签：while bsp lin 时间复杂度 利用 完成 for 多少 return
Description
给定一棵树，求每一个点能到达的最远的距离是多少
Solution
树形dp
我们利用“二次扫描与换根法”的思想，首先假定1节点为根，然后在这棵有根树上进行一次dp，求出从每一个节点出发在其子树内最远和次远距离，记为sum1,sum2
我们在定义ans[i]表示在当前这棵有根树的情况下，从i出发，到非其子树节点的最远距离是多少，那么这个点的答案就是$max\{ans[i], sum1[i]\}$
然后我们考虑“换根”
假定当前节点父亲的ans已经正确求出，那么对于当前节点，有这么几种情况：
- 其父亲的sum1不经过当前节点，那么当前节点的ans就是其父亲sum1+当前节点与父亲的距离与父亲ans+当前节点与父亲的距离的最大值
- 其父亲的sum1经过当前节点，那么当前节点的ans就是其父亲sum2+当前节点与父亲的距离与父亲ans+当前节点与父亲的距离的最大值
我们对这棵树进行两次dfs，即可完成dp
时间复杂度为$O(n)$
Code
1 #include 2 using namespace std;
3 const int maxn = 10010;
4 int n;
5 struct node {
6 int nxt, to, dis;
7 } a[maxn 1];
8 int head[maxn], num;
9 inline void add(int from, int to, int dis) {
10 a[++num].nxt = head[from];
11 a[num].to = to;
12 a[num].dis = dis;
13 head[from] = num;
14 }
15 int sum1[maxn], sum2[maxn], ans[maxn];
16 int dfs(int now, int fa) {
17 for (register int i = head[now]; i; i = a[i].nxt) {
18 int to = a[i].to;
19 if (to == fa) continue ;
20 sum2[now] = max(sum2[now], dfs(to, now) + a[i].dis);
21 if (sum2[now] > sum1[now]) swap(sum2[now], sum1[now]);
22 }
23 return sum1[now];
24 }
25 void dp(int now, int fa) {
26 for (register int i = head[now]; i; i = a[i].nxt) {
27 int to = a[i].to;
28 if (to == fa) continue ;
29 if (sum1[to] + a[i].dis == sum1[now]) {
30 ans[to] = max(sum2[now] + a[i].dis, a[i].dis + ans[now]);
31 }
32 else {
33 ans[to] = max(sum1[now] + a[i].dis, a[i].dis + ans[now]);
34 }
35 dp(to, now);
36 }
37 }
38 int main() {
39 while (~scanf("%d", &n)) {
40 num = 0;
41 memset(head, 0, sizeof(head));
42 for (register int i = 2; i i) {
43 int x, v;
44 scanf("%d%d", &x, &v);
45 add(i, x, v); add(x, i, v);
46 }
47 memset(sum1, 0, sizeof(sum1));
48 memset(sum2, 0, sizeof(sum2));
49 memset(ans, 0, sizeof(ans));
50 dfs(1, 1);
51 dp(1, 1);
52 for (register int i = 1; i i)
53 printf("%d\n", max(ans[i], sum1[i]));
54 }
55 return 0;
56 }
AC Code
【AcWing325】计算机
标签：while bsp lin 时间复杂度 利用 完成 for 多少 return
原文地址：https://www.cnblogs.com/shl-blog/p/11332726.html
评论