$$展翅翱翔之时\left(はばたきのとき\right)$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{P}3651$

题目背景

船が往くよミライへ旅立とう

船只启航 朝未来展开旅途

青い空笑ってる（なにがしたい?）

湛蓝天空露出微笑（想做些什么?）

ヒカリになろうミライを照らしたい

化作光芒吧 想就此照亮未来

輝きは心からあふれ出してもっと先の景色望むんだ

光辉自内心满溢而出 愿能望见更加前方的景色

Ah!やっと手にしたミライチケットかざして…！

Ah!挥舞起终于得手的未来门票…！ 我们Aqours，终于闪闪发亮了！

2月25和26日，将是我们登上横滨ARENA演唱的日子！

而且，还要在全日本、甚至全世界的好多影院进行转播呢！

转播好像还是通过中继卫星传输的呢！

未来ずら！

题目

不过，好像中继卫星上，出了一些问题呢……

我们的中继卫星一共有 $N$ 颗，编号成 $1$ 到 $N$ 。不过，好像一个中继卫星可以且仅可以单向地从另一颗中继卫星那儿接收数据。

第 $i$ 颗卫星现在已经被设定到了从第 $A_i$ 颗卫星 (称为接收源) 那儿接受数据。

不过这些中继卫星的接收源是可以修改的，只不过每次修改要花一定的资金呢。

听说要达成中继的话，这些卫星之间必须两两之间能够互相（直接或间接）通信才行啊。

虽然鞠莉家里很有钱，可是这么大的花费，也得提前准备一下呢。

所以，你能帮我们算算这样子一共最少要花多少钱吗？

输入

第一行 $1$ 个整数 $N$ 。

接下来 $N$ 行，每行 $2$ 个整数 $A_i,C_i$ ，表示初始时，第 $i$ 个中继卫星从第 $A_i$ 颗卫星处接收数据，以及该卫星调整接收源的所需花费。

输出

输出一个整数，表示鞠莉所需准备的最小的花费。

样例输入

4 2 2 1 6 1 3 3 1

样例输出

5

数据范围

$10\%N<=10$ $40\%N<=15$ $70\%N<=3000$ $100\%2<=N<=100000,1<=C_i<=10^9$

以下是彩蛋

事实上LoveLive的直播卫星中继只有一颗星，而且永远都是不加密的。

导致只要有一个卫星锅就可以在家偷偷看直播，也就是传说中的卫星源。

lin_toto: 万代南梦宫都把浅水湾给买了，居然只有回放，只好跑到香港the sky去看+手动滑稽。

至于为什么看转播，eplus表示LoveLive系列演唱会的票大家尽管抽选尽管抢，买得到算我输。

于是lin_toto在去年μ’s Final LoveLive的时候拿肉鸡把eplus搞趴下了，然后就买到了。

于是今年eplus连抢票都不让抢了，全抽选，抽得到算我输。

然后lin_toto就去看转播了。

思路

这道题是一道贪心，还用了个叫做“环套树”的东西。 （这个东西好像也叫做“基环树”）

我们把 $x$ 依赖 $y$ 看做 $y$ 连向 $x$ 。那就每个点的入度都是一，那就一定是环套树。 而我们最后其实就是要让这个图最后变成一个环。

那我们就可以把每一棵环套树都变成一些链，然后再把链头尾相连，就可以变成环了。 那对于每一个点，我们就贪心保留它费用最大的那个出边，其它的后换掉。

我们先找环，然后存在一个数组里面。（ 我用 $chan[i]$ 来存） 然后每个点就贪心保留它费用最大的出边。 那我们就可以处理到只剩环和环上的点连出来的一些链。

那我们就还要处理环。 我们维护两个值：一个是不断开环的费用 $ncut$ ，另一个是断开环的费用 $cut$ 。 我们要求出 $cut$ ，就两种选择，断开连入点的边或者这个点连上的链。 那断开连入点的边可以在之前的不是断开的情况下断，也可以在原来就断开的情况下断（就变成很多个链）。 而我们要求出 $ncut$ ，就只能断开这个点连上的链。 （因为这样断开环还是环，不是环的它还不是环，不会有影响）

那就把每次把答案加上 $cut$ 。

代码

#include<cstdio> #include<iostream> #define ll long long using namespace std; struct node { ll x, to, nxt; }e[100001]; ll n, x, y, le[100001], KK, tim[100001], from[100001]; ll tot, chan[100001], to[100001], ans; bool in[100001]; void add(ll x, ll y, ll z) { e[++KK] = (node){z, y, le[x]}; le[x] = KK; } void runtree(ll now) {//找到环 while (!tim[now]) {//之前没有过这个点 tim[now] = 1; now = from[now]; } while (tim[now] == 1) {//之前到过一次 tim[now] = 2; chan[++tot] = now;//记录环的每个点 now = from[now]; } } void dfs(ll now, ll fromther) {//dfs in[now] = 1; for (ll i = le[now]; i; i = e[i].nxt) if (e[i].to != fromther && tim[e[i].to] != 2) { dfs(e[i].to, now); if (e[to[now]].x > e[i].x) ans += e[i].x;//求出剪开所需费用 else { ans += e[to[now]].x; to[now] = i; } } } int main() { scanf("%lld", &n);//读入 for (ll i = 1; i <= n; i++) { scanf("%lld %lld", &x, &y);//读入 from[i] = x;//记录并建图 add(x, i, y); } for (ll i = 1; i <= n; i++) if (!in[i]) { tot = 0; runtree(i);//遍历图 if (tot == n) {//直接是一个环包括所有点 printf("0"); return 0; } for (ll j = 1; j <= tot; j++) dfs(chan[j], 0);//dfs处理树 ll ncut = 0, cut = 2147483647; for (ll j = 1; j <= tot; j++) {//枚举每个环上的点 cut = min(min(ncut, cut) + e[chan[j]].x, cut + e[to[from[chan[j]]]].x);//切开需要的费用（两个地方可以切） ncut += e[to[from[chan[j]]]].x;//不切开环 } ans += cut;//答案加上断开环要的费用 } printf("%lld", ans);//输出 return 0; }