岛屿问题

解题思路：

本题每一个点都会向外连一条出边，因此一定是一个基环森林。本题要求每个基环树中任意两点之间的距离最大值的总和。

由于是一个基环森林，里面每一棵基环树都是相互独立的，因此我们可以对于每一棵基环树，单独算一下，任意两个点之间距离的最大值，累加起来就是答案。

接下来的问题就是对于一棵基环树，如何快速求出任意两个点之间距离的最大值。我们可以将所有点对分成两类，一类是两个点属于同一棵子树，则此时这两个点的路径只会用到子树内的边，不会用到环上的边，这样就是单纯在一棵树内求任意两个点之间距离的最大值也就是求树的直径，可以用树形 $dp$ 来求，枚举子树上所有点作为最高点，求出向下走的最长路和次长路，就是经过当前点的直径，枚举所有点取一个最大值就是整棵子树的直径。

另一类就是两个点不属于同一棵子树，此时这两个点之间的路径必然会经过环，我们可以将路径分成三部分，一部分是环上的路径，另外两部分是环上任意两个点往下走的路径，由于要求最大距离，因此这三部分都要尽可能的大，而环上每个点往下走的最长距离一定是固定的，因此我们可以预处理一下环上每个点往下走的最长距离 $d_i$，然后枚举环上任意两个点 $a, b$，此时这条路径应该是 $d_a+ d_b + S_{a,b}$，其中 $S_{a,b}$ 表示 $a,b$ 之间的最长距离。这里肯定不能直接枚举环上的任意两点，太慢了，需要考虑优化。

可以发现 $S_{a, b}$ 和 $S_{b,a}$ 是相同的，因此我们可以枚举一种方向，就是设 $a$ 在 $b$ 的顺时针方向上，这样我们只需要枚举 $a$，就能枚举到环上所有的情况，此时对于任意的 $a$，我们需要在环上找到一个 $b$，使得 $d_a+d_b+S_{a,b}$ 最大，由于 $S_{a,b}$ 其实是一个区间和，因此我们可以预处理一下前缀和，设 $S_x$ 为顺时针方向的前缀和，则此时路径长度变成 $d_a+d_b+S_a-S_b$，此时 $a$ 是固定的，因此 $d_a+S_a$ 是固定的，我们只需要求 $d_b-S_b$ 的最大值，我们可以拆环成链，再将链复制一遍接在后面，若 $n$ 为环的长度，则我们每次枚举链上任意一个长度为 $n$ 的区间，都是环上的任意一个情况，我们就是要在任意一个情况中取 $d_b-S_b$ 的最大值，这就是一个滑动窗口求最值的问题。可以用单调队列来求，这样这一步也是 $O(n)$ 的时间了。

以上就是整个的思路，对于每棵基环树单独求最长距离，再累加在一起就是答案。

这里还有一个细节，对于基环树，如何找出环，这里可以用一个 $dfs$ 来找环，用一个栈记录一下我们递归的路径，当搜到路径中的某个点时，就找到环了，再把这个环取出来即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int fu[N], fw[N]; //记录每个点的父节点和它与父节点之间边的权值
bool st[N], ins[N]; //记录每个点是否被搜过，每个点是否在栈中
int cir[N], ed[N], cnt; //cir 连续的存储所有环，ed 表示每一段环的终点
LL s[N]; //s[i] 表示 i 到所在环第一个点的前缀和
LL d[N * 2], sum[N * 2]; //拆环成链后的新序列、拆环成链后的前缀和数组
int q[N * 2]; //单调队列
LL ans = 0; //记录每棵基环树的直径

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    st[u] = ins[u] = true; //标记
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(i == (from ^ 1)) continue;
        int j = e[i];
        fu[j] = u, fw[j] = w[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            cnt++;
            ed[cnt] = ed[cnt - 1];
            LL sum = w[i];
            for(int k = u; k != j; k = fu[k])
            {
                s[k] = sum;
                sum += fw[k];
                cir[++ed[cnt]] = k;
            }
            s[j] = sum, cir[++ed[cnt]] = j;
        }
    }
    ins[u] = false; //弹栈
}

LL dfs_d(int u) //统计从 u 往下走的最大距离
{
    st[u] = true;
    LL d1 = 0, d2 = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        LL dist = dfs_d(j) + w[i];
        if(dist >= d1) d2 = d1, d1 = dist;
        else if(dist > d2) d2 = dist;
    }
    ans = max(ans, d1 + d2); //情况 1
    return d1;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(i, a, b), add(a, i, b); //无向边
    }

    //找出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    memset(st, 0, sizeof st); //清空标记
    for(int i = 1; i <= ed[cnt]; i++) st[cir[i]] = true; //标记环上的点

    LL res = 0; //记录答案
    for(int i = 1; i <= cnt; i++)
    {
        ans = 0;
        int sz = 0; //记录环的大小
        for(int j = ed[i - 1] + 1; j <= ed[i]; j++) //找出环中所有点
        {
            int k = cir[j];
            d[sz] = dfs_d(k);
            sum[sz] = s[k];
            sz++;
        }
        //拆环成链
        for(int j = 0; j < sz; j++)
            d[sz + j] = d[j], sum[sz + j] = sum[j] + sum[sz - 1];

        //单调队列
        int hh = 0, tt = -1;
        for(int j = 0; j < sz * 2; j++)
        {
            if(hh <= tt && j - q[hh] + 1 > sz) hh++;
            if(hh <= tt) ans = max(ans, d[j] + sum[j] + d[q[hh]] - sum[q[hh]]); //情况2
            while(hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt--;
            q[++tt] = j;
        }
        res += ans; //累加答案
    }
    printf("%lld\n", res);

    return 0;
}