ZJOI2008-骑士

题目

luoguP2607

bzoj1040

题解

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

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

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

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

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

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

==两个注意事项==

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

处理重边的方法：

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

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

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

代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
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;}
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 7;

int curx, cury;
bool vis[MAXN];
vector<int> G[MAXN];
ll dp[MAXN][2];
int val[MAXN];
void dfs(int x, int fa){
    if(vis[x]){
        curx = x;
        cury = fa;
        return;
    }
    vis[x] = 1;
    for(int i = 0; i < G[x].size(); ++i){
        int u = G[x][i];
        if(u == fa) continue;
        dfs(u, x);
    }
}
void go(int x, int fa){
    dp[x][0] = 0; dp[x][1] = val[x];
    for(int i = 0; i < G[x].size(); ++i){
        int u = G[x][i];
        if(u == fa) continue;
        if(x == curx && u == cury)  continue;
        if(u == curx && x == cury)  continue;
        go(u, x);
        dp[x][0] += max(dp[u][0], dp[u][1]);
        dp[x][1] += dp[u][0];
    }
}
int main(){
    #ifndef ONLINE_JUDGE         
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif 
    
    int n, x;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &val[i], &x);
        G[x].push_back(i);
        G[i].push_back(x);
    }
    ll res = 0, tmp;
    for(int i = 1; i <= n; ++i){
        if(vis[i])  continue;
        dfs(i, 0);
        // cout << curx << ' ' << cury << endl;
        // cout << count(G[curx].begin(), G[curx].end(), cury) << endl;
        if(count(G[curx].begin(), G[curx].end(), cury) == 2){
            go(curx, 0);
            go(cury, 0);
            res += max(dp[curx][0] + dp[cury][1], dp[curx][1] + dp[cury][0]);
            continue;
        }
        go(curx, 0);
        tmp = dp[curx][0];
        go(cury, 0);
        tmp = max(tmp, dp[cury][0]);
        res += tmp;
    }
    printf("%lld\n", res);
    return 0;
}