bzoj1040 [ZJOI2008]骑士(环套树+树形dp)

环套树的dp的样子。
由于每个骑士都有一个憎恨关系,所以保证了每个点只有一条出边。
然后对于一个树,可以保证它有且仅有一个环的样子(否则没有)。对于一个这样的森林,我们先查找所有的联通块,可以通过简单的一次遍历找到环,我们只需要确定环上某2点为基,然后以这2个点为根分别进行树形dp即可。树形dp还是老套路:

$$dp[0][fa]=\sum max(dp[1][son],dp[0][son])$$

$$dp[1][fa]=cost(fa)+\sum dp[0][son]$$

如何保证一定不同时选环上两点呢?我们$(u,v)$为例,答案一定是$max{ dp[0][u],dp[0][v]}$。因为不同时选$(u,v)$时,以任意点为根如果选了这个点,我们都不知道较大的答案是否包括了另一个不应同时被选的点,所以只需要都不选的情况下$dp$就好啦。

如何保证任取环上两点,一定能得到对应子树的答案呢?环是联通的,断掉一条边一定使得这个联通块成为一棵树,然后树形dp的话肯定是可以得到答案的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1000000+5;
int head[maxn<<1],eg[maxn<<1],nxt[maxn<<1];
pair<int ,int > kg;
int cnt=0,n;
int tag;
bool vis[maxn],kgm[maxn];
ll c[maxn];
void addedge(int from,int to)
{
eg[++cnt]=to;nxt[cnt]=head[from];head[from]=cnt;
}
void dfs(int v,int fa)
{
vis[v]=true;
for(int i=head[v];i>0;i=nxt[i])
{
if(eg[i]==fa)continue;
if(vis[eg[i]]){
tag=i;kg.first=v;kg.second=eg[i];continue;
}
dfs(eg[i],v);
}
}
ll dp[2][maxn];
bool hav[maxn];
ll treedp(int v,int chos,int fa)
{
if(hav[v]) return dp[chos][v];
dp[0][v]=0;
dp[1][v]=c[v];
for(int i=head[v];i>0;i=nxt[i])
{
if(i==tag || ((i&1)?i+1:i-1)==tag)continue;
if(eg[i]==fa) continue;
int to=eg[i];
dp[0][v]+=max(treedp(to,0,v),treedp(to,1,v));
dp[1][v]+=treedp(to,0,v);
}
hav[v]=true;
return dp[chos][v];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int to;
scanf("%lld%d",&c[i],&to);
addedge(i,to);addedge(to,i);
}
ll ans=0;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
{
if(!vis[i]){
ll del=0;
dfs(i,-1);
ll tim;
memset(hav,0,sizeof(hav));
del=max(del,(tim=treedp(kg.first,0,-1)));
memset(hav,0,sizeof(hav));
del=max(del,(tim=treedp(kg.second,0,-1)));
ans+=del;
}
}
printf("%lld\n",ans);
return 0;
}