题目#

luoguP2607

bzoj1040

题解#

基环树就是一颗多了一条边的树，多了这条边，就会产生一个环。

考虑找到这个环上的任意一条边，断掉这条边，然后图形就又变回了树。（可以证明，断环上的哪条边对结果并没有影响）

然后分别都被断掉的这条边的两个端点u、v，做树形动规。

$dp[i][0/1]$ 表示取不取第 $i$ 个点的最大值。

这和luoguP1352，没有上司的舞会一样。

则这颗基环树的最大值为 $max(dp[u][0], dp[v][0])$ ，当然因为树形动规的特点，一次动规是不能同时求出这两个值的，因此要分别对u、v进行动规。

==两个注意事项==

非常重要的一点是，两个骑士可能互相憎恨，因此会存在重边，需要特判。
记得开long long。

处理重边的方法：

按照我的建图方式，如果存在重边<u，v>，那么u的可到点集合中会出现两次v。

根据这个特点就可以进行特判了。

另外，这份代码在最后一个测试点TLE了。

代码#

1
// luogu-judger-enable-o2
2
#include <bits/stdc++.h>
3
using namespace std;
4
typedef long long ll;
5
typedef pair<int, int > pii;
6
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
7
const int mod = 1e9 + 7;
8
const int MAXN = 1e6 + 7;
9

10
int curx, cury;
11
bool vis[MAXN];
12
vector<int> G[MAXN];
13
ll dp[MAXN][2];
14
int val[MAXN];
15
void dfs(int x, int fa){
16
    if(vis[x]){
17
        curx = x;
18
        cury = fa;
19
        return;
20
    }
21
    vis[x] = 1;
22
    for(int i = 0; i < G[x].size(); ++i){
23
        int u = G[x][i];
24
        if(u == fa) continue;
25
        dfs(u, x);
26
    }
27
}
28
void go(int x, int fa){
29
    dp[x][0] = 0; dp[x][1] = val[x];
30
    for(int i = 0; i < G[x].size(); ++i){
31
        int u = G[x][i];
32
        if(u == fa) continue;
33
        if(x == curx && u == cury)  continue;
34
        if(u == curx && x == cury)  continue;
35
        go(u, x);
36
        dp[x][0] += max(dp[u][0], dp[u][1]);
37
        dp[x][1] += dp[u][0];
38
    }
39
}
40
int main(){
41
    #ifndef ONLINE_JUDGE
42
        freopen("in.txt", "r", stdin);
43
        freopen("out.txt", "w", stdout);
44
    #endif
45

46
    int n, x;
47
    scanf("%d", &n);
48
    for(int i = 1; i <= n; ++i){
49
        scanf("%d %d", &val[i], &x);
50
        G[x].push_back(i);
51
        G[i].push_back(x);
52
    }
53
    ll res = 0, tmp;
54
    for(int i = 1; i <= n; ++i){
55
        if(vis[i])  continue;
56
        dfs(i, 0);
57
        // cout << curx << ' ' << cury << endl;
58
        // cout << count(G[curx].begin(), G[curx].end(), cury) << endl;
59
        if(count(G[curx].begin(), G[curx].end(), cury) == 2){
60
            go(curx, 0);
61
            go(cury, 0);
62
            res += max(dp[curx][0] + dp[cury][1], dp[curx][1] + dp[cury][0]);
63
            continue;
64
        }
65
        go(curx, 0);
66
        tmp = dp[curx][0];
67
        go(cury, 0);
68
        tmp = max(tmp, dp[cury][0]);
69
        res += tmp;
70
    }
71
    printf("%lld\n", res);
72
    return 0;
73
}