【AcWing325】计算机

骑猪看日落 2023-06-05 08:51 1阅读 0赞

### Description ###

给定一棵树，求每一个点能到达的最远的距离是多少

### Solution ###

树形dp

我们利用“二次扫描与换根法”的思想，首先假定1节点为根，然后在这棵有根树上进行一次dp，求出从每一个节点出发在其子树内最远和次远距离，记为sum1,sum2

我们在定义ans\[i\]表示在当前这棵有根树的情况下，从i出发，到非其子树节点的最远距离是多少，那么这个点的答案就是$max\\\{ans\[i\], sum1\[i\]\\\}$

然后我们考虑“换根”

假定当前节点父亲的ans已经正确求出，那么对于当前节点，有这么几种情况：

1.  其父亲的sum1不经过当前节点，那么当前节点的ans就是其父亲sum1+当前节点与父亲的距离与父亲ans+当前节点与父亲的距离的最大值
2.  其父亲的sum1经过当前节点，那么当前节点的ans就是其父亲sum2+当前节点与父亲的距离与父亲ans+当前节点与父亲的距离的最大值

我们对这棵树进行两次dfs，即可完成dp

时间复杂度为$O(n)$

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     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 <= n; ++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 <= n; ++i) 
    53             printf("%d\n", max(ans[i], sum1[i]));
    54     }
    55     return 0;
    56 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11332726.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/214996e8195840d4bdfafe2931e6611f.png