欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ZROJ#398. 【18提高7】随机游走(期望dp 树形dp)

程序员文章站 2022-06-15 15:05:44
题意 ~~[题目链接]~~版权原因就不发了。。 给出一棵树,求出任意两点之间期望距离的最大值 Sol 比较清真的一道题吧。。 设$f[x]$表示从$x$走到$x$的父亲的期望步数 $g[x]$表示从父亲走来的期望步数 $d[x]$表示$x$节点的度数 不难得到方程$f[x] = \sum_{to \ ......

题意

[题目链接]版权原因就不发了。。

给出一棵树,求出任意两点之间期望距离的最大值

sol

比较清真的一道题吧。。

\(f[x]\)表示从\(x\)走到\(x\)的父亲的期望步数

\(g[x]\)表示从父亲走来的期望步数

\(d[x]\)表示\(x\)节点的度数

不难得到方程\(f[x] = \sum_{to \in son[x]} f[to] + d[x]\)

\(g[x] = g[fa[x]] + \sum_{to \in son[fa[x]] \text{且} to \not = x} f[to] + d[fa[x]]\)

最后计算的时候维护向上向下最大值即可

当然,仔细观察不难发现\(f[x]\)即为子树中所有节点的度数

\(g[x]\)为整棵树中除子树外节点的度数

考虑每条边的贡献后不难得到

\(f[x] = 2 * siz[x] - 1\)

\(g[x] = 2 * (n - siz[x]) - 1\)

#include<bits/stdc++.h>
#define chmax(a, b) (a = a > b ? a : b)
#define ll long long 
const int maxn = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
std::vector<int> v[maxn];
int n, up[maxn], down[maxn], d[maxn], siz[maxn], ans, f[maxn], g[maxn];
void dfs3(int x, int fa) {
    siz[x] = 1;
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == fa) continue;
        dfs3(to, x);
        siz[x] += siz[to];
        
        ans = std::max(ans, std::max(up[x] + g[to] + down[to], down[x] + f[to] + up[to]));
        chmax(up[x], up[to] + f[to]);
        chmax(down[x], down[to] + g[to]);
    //  chmax(ans, up[x] + down[x]);
    }
    f[x] = (siz[x] << 1) - 1;
    g[x] = ((n - siz[x]) << 1) - 1;
}
int main() {
    n = read();
    for(int i = 1; i < n; i++) {
        int x = read(), y = read(); d[x]++; d[y]++;
        v[x].push_back(y); v[y].push_back(x); 
    }
    dfs3(1, 0);
    printf("%lld", ans); puts(".00000");
    return 0;
}