嘟嘟嘟
一句话题意：求带权基环树森林中每一个联通块的最长路之和，路径为简单路径。
其实这道题不难，只不过是吧好多知识拼接在了一起。
看到基环树，就会想到断环为链，为了能枚举到所有路径，要把链翻倍乘2。
现在得到了一个序列，上面的每一个点表示外向树的树根。
那么一条最长路可能有两种情况：
1.单独在一个外向树内部：
dp一下，维护最长链和次长链即可。
2.起点和终点分别在两棵树内：
还是先dp一下，求出到树根的最长距离。
然后暴力的做法就是(O(n ^ 2))枚举起点终点所在外向树，但这肯定会超时。
考虑dp。令(f[i])表示到根结点(i)的最长路，(dis(i, j))表示环上(i, j)两点之间的距离（前缀和维护），则很容易搞出
[dp[i] = max_{j = i - n + 1} ^ {i - 1} (f[j] + dis(i, j)) + f[i]
]
但是这还是(O(n ^ 2))的，于是这也得优化。
单调队列就行啦。
需要注意的是，每一次比较的不仅仅是(f[i])，应该是(f[q[l]] + dis(q[l], i + 1))和(f[i] +dis(i, i + 1))，因为dp式是这样的嘛。
然后对于每一个联通块，两种情况取max。
耐心点写就行
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
struct Edge
{
int nxt, to; ll w;
}e[maxn << 1];
int head[maxn], ecnt = -1;
void addEdge(int x, int y, ll w)
{
e[++ecnt] = (Edge){head[x], y, w};
head[x] = ecnt;
}
bool vis[maxn];
struct Node
{
int E, v;
}st[maxn];
int top = 0;
bool in[maxn], cir[maxn];
int a[maxn], tot = 0;
ll sum[maxn];
void dfs_cir(int now, int _e)
{
vis[now] = in[now] = 1;
st[++top] = (Node){_e, now};
for(int i = head[now], v; i != -1; i = e[i].nxt)
{
if(in[v = e[i].to] && (i ^ 1) != _e)
{
int j = top;
for(; st[j].v != v; --j) a[++tot] = st[j].v, sum[tot + 1] = sum[tot] + e[st[j].E].w;
a[++tot] = st[j].v; sum[tot + 1] = sum[tot] + e[i].w; a[tot + 1] = a[1];
for(int j = 2; j <= tot; ++j) a[tot + j] = a[j], sum[tot + j] = sum[tot + j - 1] + sum[j] - sum[j - 1];
}
if(vis[v]) continue;
dfs_cir(v, i);
}
in[st[top--].v] = 0;
}
ll f[maxn], _ans = 0;
void dfs(int now, int _f)
{
ll Max1 = 0, Max2 = 0;
for(int i = head[now], v; i != -1; i = e[i].nxt)
{
if((v = e[i].to) == _f || cir[v]) continue;
dfs(v, now);
f[now] = max(f[now], f[v] + e[i].w);
if(f[v] + e[i].w > Max1) Max2 = Max1, Max1 = f[v] + e[i].w;
else Max2 = max(Max2, f[v] + e[i].w);
}
_ans = max(_ans, Max1 + Max2);
}
ll dp[maxn];
int q[maxn], l = 1, r = 0;
ll solve(int now)
{
top = tot = _ans = 0;
dfs_cir(now, -1);
for(int i = 1; i <= tot; ++i) cir[a[i]] = 1;
for(int i = 1; i <= tot; ++i) dfs(a[i], 0);
ll Max = 0; q[1] = 0; l = 1; r = 0;
for(int i = 1; i <= (tot << 1); ++i)
{
while(l <= r && i - q[l] >= tot) l++;
dp[i] = f[a[q[l]]] + f[a[i]] + sum[i] - sum[q[l]];
while(l <= r && f[a[q[r]]] + sum[i + 1] - sum[q[r]] < sum[i + 1] - sum[i] + f[a[i]]) r--;
q[++r] = i;
Max = max(Max, dp[i]);
}
return max(_ans, Max);
}
int main()
{
Mem(head, -1);
n = read();
for(int i = 1; i <= n; ++i)
{
int y = read(), w = read();
addEdge(i, y, w); addEdge(y, i, w);
}
ll ans = 0;
for(int i = 1; i <= n; ++i) if(!vis[i]) ans += solve(i);
write(ans), enter;
return 0;
}