可以说是很妙了

Problem

求基环树森林联通块的直径之和

Solution

https://www.luogu.org/blog/larryzhong/solution-p4381

看题解做的

最近几天的题好像都看了题解

反思...

妙的地方有几个：

• 换了个方式维护基环树的边，就很妙，很舒服
• 一般来说把基环树的环当作树的根
• 式子变形，找到不变量

Code

// Code by ajcxsu
// Problem: island

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void gn(int &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=1e6+10;
int h[N], to[N], nexp[N], W[N], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
int w[N], fa[N];

bool vis[N], cir[N];
ll S, s[N], d[N][2], f[N];
void dp(int x) {
    vis[x]=true;
    for(int u=h[x];u;u=nexp[u])
        if(!cir[to[u]]) {
            dp(to[u]);
            if(d[to[u]][0]+W[u]>d[x][0]) d[x][1]=d[x][0], d[x][0]=d[to[u]][0]+W[u];
            else if(d[to[u]][0]+W[u]>d[x][1]) d[x][1]=d[to[u]][0]+W[u];
            f[x]=max(f[to[u]], f[x]);
        }
    f[x]=max(f[x], d[x][0]+d[x][1]);
}

ll tot;
void fcir(int x) {
    int rt=x;
    vis[x]=1;
    while(!vis[fa[rt]]) {
        rt=fa[rt], vis[rt]=1;
    } // find circle
    int na=rt;
    ll nw=0;
    while(fa[na]!=rt) {
        cir[na]=true;
        nw+=w[na], na=fa[na];
        s[na]=nw;
    } // mark
    nw+=w[na], S=nw, cir[na]=true;
    ll nans=0, a=-0x7ffffffffffffll, b=-0x7fffffffffffll;
    na=rt;
    do {
        dp(na);
        nans=max(nans, max(d[na][0]+s[na]+a, S+d[na][0]-s[na]+b));
        nans=max(nans, f[na]);
        a=max(a, d[na][0]-s[na]);
        b=max(b, d[na][0]+s[na]);
        na=fa[na];
    } while(na!=rt);
    tot+=nans;
}

int main() {
    int n;
    gn(n);
    int u,v;
    for(int i=1;i<=n;i++) {
        gn(u), gn(v);
        ins(u, i, v);
        fa[i]=u, w[i]=v;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]) {
            fcir(i);
        }
    printf("%lld\n", tot);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4381.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆