BZOJ 4346 Nadajniki

发表于 | 更新于

Link

被这道题前前后后克了10h。 我也实在不想回头看这道题目了 但是为了让这10h有意义 我还是硬着头皮写点东西吧。

Solution

树形DP 最暴力的状态是f[pos][i][j][k]f[pos][i][j][k]表示在以pospos为根的子树中，pospos的父节点至少安装ii个，pospos安装了jj个，pospos的子节点安装了kk个的最小代价。 优化一下，拆成三个 g[pos][i]g[pos][i]表示在以pospos为根的子树中，表示pospos不安装，pospos的子节点安装了ii个的最小代价 h[pos][i]h[pos][i]表示pospos安装了ii个的最小代价 r[pos][i]r[pos][i]表示pospos不安装，需要父节点安装至少ii个的最小代价 在DP中，还需要一个辅助的状态f[pos][i][j]f[pos][i][j]，表示在以pospos为根的子树中，pospos不安装，pospos的子节点安装了ii个，父节点安装了jj个的最小代价 显然g[pos][i]=min{f[pos][i][j],j≤i}g[pos][i]=\min \{f[pos][i][j],j \le i\} r[pos][i]=min{f[pos][j][j+i]}r[pos][i]=\min\{f[pos][j][j+i]\} h[pos][i]=min{min{g[pos][j]},min{r[pos][1∼i]}}h[pos][i]=\min \{\min\{g[pos][j]\},\min\{r[pos][1\sim i]\}\} 然后剩下的问题就是转移f[][][]f[][][]了 要用每个子节点优化，在寻找最优方案的过程中不能把原数组覆盖，要在一个f′[][][]f'[][][]中计算，最后再 过去。 所以转移就两种情况： 1.让子节点多安装 2.让父节点多安装。 那就枚举每个状态f[pos][i][j]f[pos][i][j]，枚举kk——需要多安装几个 1.f[pos][i][j]+h[u][k]→f′[pos][min{i+k,2}][j]1.f[pos][i][j]+h[u][k]\rightarrow f'[pos][\min \{i+k,2\}][j] 2.f[pos][i][j]+g[u][k]→f′[pos][i][max{2−k,j}]2.f[pos][i][j]+g[u][k]\rightarrow f'[pos][i][\max\{2-k,j\}] 第一个转移里面的min\min很显然：一个点安装两个以上是完全意义不明的 第二个转移的含义相当于多选了孙子节点，就需要多选父节点——根据题意可以感受一下。至于第二个里面的max\max，考虑一下f[pos][i][j]f[pos][i][j]的i+ji+j肯定是需要≥2\ge 2的，否则肯定是不合法的状态。这样做就可以使得合法的值不会进入不合法的状态。好吧其实我也搞不清楚为什么 只是为了让这个状态在增加了一个子树之后变得合法。

Tips

一开始想DP每个点到父节点的连边的代价，导致非常麻烦 费力写出来之后发现有些情况没有考虑 唉还能说什么呢人太弱只能被虐 以后还是慎重考虑在树形DP中DP点到父节点的值吧 花这么久也是醉了 也许以后被克许久之后应该早点看题解？

Code

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 "lucida"
using std::min;
using std::max;
using std::pair;
using std::make_pair;

template <class T> inline T min(const T &a,const T &b,const T &c) {return min(a,min(b,c));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d){return min(a,min(b,c,d));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e){return min(a,min(b,c,d,e));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e,const int &f){return min(a,min(b,c,d,e,f));}
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d,const T &e,const int &f,const int &g){return min(a,min(b,c,d,e,f,g));}


const int MAXN=200000+11,INF=0x1f1f1f1f;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t);
}*id[MAXN];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
struct FSMin {
	pair<int,int> v[2];
	FSMin() {
		v[0]=v[1]=make_pair(INF,-1);
	}
	pair<int,int> &operator [](int x){
		return v[x];
	}
	void operator <<(pair<int,int> nv) {
		if(v[0]>nv) {
			v[1]=v[0];
			v[0]=nv;
		} else if(v[1]>nv) {
			v[1]=nv;
		}
	}
};

int f[MAXN][3][3],g[MAXN][3],p[MAXN][3],r[MAXN][3],fa[MAXN],temp[3][3];
void DP(int pos,int fa=0) {
	p[pos][1]=1,p[pos][2]=2;
	f[pos][0][0]=0;
	for(Edge *e=id[pos];e;e=e->pre) if(e->to!=fa) {
		int u=e->to;
		DP(u,pos);
		p[pos][1]+=min(p[u][1],p[u][2],g[u][0],g[u][1],g[u][2],r[u][1]);
		p[pos][2]+=min(p[u][1],p[u][2],g[u][0],g[u][1],g[u][2],r[u][1],r[u][2]);
		memset(temp,31,sizeof(temp));
		for(int i=0;i<=2;++i)
			for(int j=0;j<=2;++j) {
				for(int k=1;k<=2;++k) chkmn(temp[min(i+k,2)][j],f[pos][i][j]+p[u][k]);
				for(int k=0;k<=2;++k) chkmn(temp[i][max(2-k,j)],f[pos][i][j]+g[u][k]);
			}
		 memcpy(f[pos],temp,sizeof(temp));
	}
	for(int i=0;i<=2;++i)
		for(int j=0;j<=i;++j)
			chkmn(g[pos][i],f[pos][i][j]);
	r[pos][1]=min(f[pos][0][1],f[pos][1][2]);
	r[pos][2]=f[pos][0][2];
}
int main() {
	freopen("input","r",stdin);
	memset(f,31,sizeof(f));
	memset(g,31,sizeof(g));
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int a,b;
		is>>a>>b;
		Adde(a,b);
	}
	DP(1);
	int Ans=min(p[1][1],p[1][2],g[1][0],g[1][1],g[1][2]);
	os<<Ans<<'\n';
	return 0;
}