「ZJOI2008」骑士

发表于 | 分类于 | | 浏览量： 次

好一个树形DP。

传送门

洛谷P2607

BZOJ1040

题解

他出题人要是敢去掉一条边，我就敢做！！！

首先对于每一个骑士，向他最痛恨的人建一条边。

如果只有$n-1$条边的话，就是一个裸的带权的树上最大独立集。

但是由于要$n$条边，所以最后建出来的应该是一个基环内向树森林。

比如这样：

1.png

对于在环上的每一个点，可以直接DP出该点选与不选时它与它的子树的最大权值和。

对于环，我们可以再来一趟DP，定义$G[i][0/1/2/3]$：

  • $G[i][0]$环上第一个点可以选，第$i$个点选时的最大权值和。

  • $G[i][1]$环上第一个点可以选，第$i$个点不选时的最大权值和。

  • $G[i][2]$环上第一个点不可以选，第$i$个点选时的最大权值和。

  • $G[i][3]$环上第一个点不可以选，第$i$个点不选时的最大权值和。

最后的答案为$max(G[n][0],G[n][2],G[n][3])​$。

对于每一个环，分别DP，然后把答案加在一起即可。

复杂度：$\Theta(n)$。

代码

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
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=1000005;
int n,A[maxn],fa[maxn],in[maxn],len,C[maxn];vector <int> so[maxn];LL ans,G[maxn][4],F[maxn][2];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void Toposort()   //拓扑排序找环+建图
{
	static int que[maxn],hed,til;
	for(int i=1;i<=n;i++)
		if(in[i]==0)
			que[++til]=i;
	while(hed!=til)
	{
		hed++;
		in[fa[que[hed]]]--;
		so[fa[que[hed]]].push_back(que[hed]);
		if(!in[fa[que[hed]]]) que[++til]=fa[que[hed]];
	}
}
void DFS(int now,int fa)
{
	F[now][1]=A[now];
	for(int i=0;i<(int)so[now].size();i++)
	{
		DFS(so[now][i],now);
		F[now][1]+=F[so[now][i]][0];
		F[now][0]+=max(F[so[now][i]][0],F[so[now][i]][1]);
	}
}
void GetCircle(int now)
{
	if(in[fa[now]]==0) return;
	C[++len]=now;
	in[fa[now]]--;
	GetCircle(fa[now]);
}
void Solve()                //对于每个环分别DP
{
	G[1][0]=F[C[1]][0];
	G[1][1]=F[C[1]][1];
	G[1][2]=F[C[1]][0];
	G[1][3]=0;
	for(int i=2;i<=len;i++)
	{
		G[i][0]=G[i][2]=F[C[i]][0];
		G[i][1]=G[i][3]=F[C[i]][1];
		G[i][0]+=max(G[i-1][0],G[i-1][1]);
		G[i][1]+=G[i-1][0];
		G[i][2]+=max(G[i-1][2],G[i-1][3]);
		G[i][3]+=G[i-1][2];
	}
	ans+=max(G[len][0],max(G[len][2],G[len][3]));
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		A[i]=read();
		fa[i]=read();
		in[fa[i]]++;
	}
	Toposort();
	for(int i=1;i<=n;i++) if(in[i]>0) DFS(i,0);
	for(int i=1;i<=n;i++)
	{
		if(in[i]>0)
		{
			len=0;
			GetCircle(i);
			Solve();
		}
	}
	printf("%lld\n",ans);
	return 0;
}