不算难的一道题。
思路
考虑原图是一个基环树。
首先在树上部分的路径是固定的，我们没有办法抉择。
唯一需要考虑的是在环上的那一部分。
在环上我们每一个路径有两种选择。
如何考虑到所有情况。
我们每一次断掉环上的一条边。
这样每一个路径就变成固定的了。
我们只需要快速计算贡献就可以。
贡献形如一个区间覆盖，区间消除覆盖，查询每覆盖的点的权值。
这是一个经典问题。
我们可以维护覆盖次数的最小值，与最小值代表的权值。
这样可以快速维护没有被覆盖的位置的和。
时间复杂度：\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, ct, tt;
int fa[N], tp[N], vs[N];
int vl[N], dp[N], id[N], sm[N], head[N];
int ff[N][20];
int st[N << 1], pv[N << 1];
int mi[N << 2], tg[N << 2];
long long tr[N << 2];
long long sum;
struct edge {
int to, nxt, val;
} e[N << 1];
vector<int> ad[N << 1];
vector<int> dl[N << 1];
inline bool dfs1(int x, int f) {
vs[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
if ((i ^ 1) == f) continue;
if (vs[e[i].to]) {
for (int j = x; j != e[i].to; j = fa[j])
++tt, st[tt] = j, pv[tt] = vl[j];
++tt, st[tt] = e[i].to, pv[tt] = e[i].val;
return 1;
} else {
fa[e[i].to] = x;
vl[e[i].to] = e[i].val;
if (dfs1(e[i].to, i)) return 1;
}
}
return 0;
}
inline void dfs2(int x, int f, int t, int v) {
fa[x] = ff[x][0] = f, dp[x] = dp[f] + 1, tp[x] = t, vl[x] = v;
for (int i = 1; i <= 19; i++) ff[x][i] = ff[ff[x][i - 1]][i - 1];
for (int i = head[x]; i; i = e[i].nxt)
if (!vs[e[i].to] && e[i].to != f)
dfs2(e[i].to, x, t, e[i].val);
}
inline int lca(int x, int y) {
if (dp[x] < dp[y]) swap(x, y);
for (int i = 19; i >= 0; i--) if (dp[ff[x][i]] >= dp[y]) x = ff[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--) if (ff[x][i] != ff[y][i]) x = ff[x][i], y = ff[y][i];
return fa[x];
}
inline void dfs3(int x, int f) {
for (int i = head[x]; i; i = e[i].nxt) {
if (vs[e[i].to] || e[i].to == f) continue;
dfs3(e[i].to, x);
sm[x] += sm[e[i].to];
}
if (sm[x]) sum += vl[x];
}
inline void pup(int p, int mid) {
tr[p] = 0;
mi[p] = min(mi[mid<<1], mi[mid<<1|1]);
if (mi[p] == mi[mid<<1]) tr[p] += tr[mid<<1];
if (mi[p] == mi[mid<<1|1]) tr[p] += tr[mid<<1|1];
}
inline void build(int p, int l, int r) {
if (l == r) tr[p] = pv[l];
else {
int mid = (l + r) >> 1;
build(mid<<1, l, mid);
build(mid<<1|1, mid + 1, r);
pup(p, mid);
}
}
inline void psh(int p, int k) { tg[p] += k, mi[p] += k; }
inline void pdo(int p, int mid) {
if (tg[p]) {
psh(mid<<1, tg[p]);
psh(mid<<1|1, tg[p]);
tg[p] = 0;
}
}
inline void upd(int p, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) psh(p, k);
else {
int mid = (l + r) >> 1;
pdo(p, mid);
if (mid >= L) upd(mid<<1, l, mid, L, R, k);
if (mid < R) upd(mid<<1|1, mid + 1, r, L, R, k);
pup(p, mid);
}
}
int main() {
cin >> n >> m, ct = 1;
for (int i = 1; i <= n; i++) {
int a, c;
cin >> a >> c;
e[++ct] = {i, head[a], c}, head[a] = ct;
e[++ct] = {a, head[i], c}, head[i] = ct;
}
dfs1(1, 0);
for (int i = 1; i <= n; i++) vs[i] = 0;
for (int i = 1; i <= tt; i++) vs[st[i]] = 1;
for (int i = 1; i <= tt; i++) dfs2(st[i], 0, st[i], 0);
for (int i = 1; i <= tt; i++) {
st[i + tt] = st[i];
pv[i + tt] = pv[i], id[st[i]] = i;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
if (id[tp[x]] > id[tp[y]]) swap(x, y);
if (tp[x] == tp[y]) {
sm[x]++;
sm[y]++;
sm[lca(x, y)] -= 2;
} else {
sm[x]++;
sm[y]++;
ad[id[tp[y]]].push_back(id[tp[x]]);
dl[id[tp[x]]].push_back(id[tp[y]]);
ad[id[tp[x]] + tt].push_back(id[tp[y]]);
dl[id[tp[y]]].push_back(id[tp[x]] + tt);
ad[id[tp[y]] + tt].push_back(id[tp[x]] + tt);
}
}
for (int i = 1; i <= tt; i++) dfs3(st[i], 0);
long long all = 0;
long long ans = 1e18;
for (int i = 1; i <= tt + tt; i++) all += pv[i];
build(1, 1, tt + tt);
for (int i = 1; i <= tt; i++)
for (auto j : ad[i]) upd(1, 1, tt + tt, j, i - 1, 1);
for (int i = 1; i <= tt; i++) {
ans = min(ans, sum + all - tr[1]);
for (auto j : ad[i + tt]) upd(1, 1, tt + tt, j, i + tt - 1, 1);
for (auto j : dl[i]) upd(1, 1, tt + tt, i, j - 1, -1);
}
cout << ans << "\n";
}