BZOJ 3829 FarmCraft

发表于 | 更新于

Link

Solution

可以看出，每个点的子树怎么装最快是一个独立的子问题。 所以现在考虑的就是在每个根节点如何安排每个子树的安装顺序 每个子树uu最后完成的时间t[u]t[u]，是进入的时间+f[u]+f[u]。 而整个子树完成的时间，是max{t[u]}\max\{t[u]\} 子树进入的时间是遍历完之前所有子树的时间 一开始的想法是： 如果本身装机时间就长，还要等别的子树，那肯定最后是最慢的？ 于是就按照装机时间排序贪心，WA。 考虑一种极端情况：有一个超大的子树，每个点安装的时间都是00，但是遍历很慢，凭此rank1。如果先安装了这个，别的就白等了。 于是启发采用新的策略：按照f[u]−(sz[u]−1)∗2f[u]-(sz[u]-1)*2排序，也就是子树安装的时间除去遍历的时间。这样就对了。 具体地说 有一个pairpair的序列s[]s[]，每个s[i]s[i]对答案的贡献是s[i].first+∑j<is[j].seconds[i].first+\sum\limits_{j< i} s[j].second 则Ans=max{s[i].first+∑j<is[j].second}Ans=\max\{s[i].first+\sum\limits_{j< i} s[j].second\} 设最大值在点uu取得，设uu与vv交换可以使得最大值在vv取得且变小 s[u].first+∑s[u′∣u′<u].seconds[u].first+\sum s[u'|u' < u].second 感觉不靠谱。。。能否给个证明。。

Tips

如果可能的话，要科学地贪心。 想一些具体的边界情况试着叉掉做法。

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
#include "lucida"
using std::pair;
using std::make_pair;
using std::sort;
using std::greater;
using std::max;
const int MAXN=500000+11;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
}*id[MAXN];
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
int c[MAXN],sz[MAXN];
int64 f[MAXN];
int64 DP(int pos,int fa) {
	sz[pos]=1;
	f[pos]=c[pos];
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa) {
			int u=e->to;
			DP(u,pos);
			sz[pos]+=sz[u];
		}
	static pair<int64,int> son[MAXN];
	int sc=0;
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa) {
			int u=e->to;
			son[++sc]=make_pair(f[u]-(sz[u]-1)*2,(sz[u]-1)*2);
		}
	sort(son+1,son+1+sc,greater<pair<int64,int> >());
	int64 res=0,sum=1; 
	for(int i=1;i<=sc;++i) {
		chkmx(res,sum+son[i].first+son[i].second);
		sum+=son[i].second+2;
	}
	chkmx(f[pos],res);
	return f[pos];
}

int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n;++i)
		is>>c[i];
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	int64 Ans=max((int64)c[1]+(n-1)*2,DP(1,0));
	os<<Ans<<'\n';
	return 0;
}