POI2013 Polarization

POI
想法, 树的重心, 背包

POI2013 Polarization

题目大意：

给定一棵树，可以对每一条边定向成一个有向图，这张有向图的可达点对数为树上有路径从u到达v的点对(u,v)的个数。求最小可达点对数和最大可达点对数。

题解：

最小值比较显然：首先一条边必然可以产生一个点对，那么可能存在的最小的可达点对数为n-1。接下来可以证明n-1必然可行：依层分别为树染色，奇层黑、偶层白，边只从黑点连向白点，那么可以发现只有n-1条边所对应的点对满足，从而可知，最小值为n-1。

最大值比较难，首先有一个结论:

一定以重心为根，任意一个子树要么全部指向根，要么全部背离根。

哪位神牛会证明，别忘了教我

设指向根的节点数为k1，背离的为k2，那么答案即为$\sum (son_p -1) +k1 \times k2$.

$\sum (son_p -1)$ 已经固定了，那么对答案贡献就看k1与k2了。

首先联想到的肯定是背包，定义dp[i]表示是否能有i个点指向根。之后考虑每一个点取不取。

但这样写复杂度并不能保证。如果遇到了“菊花图”，复杂度将退化为$O(n^2)$.

于是我们分块决策：

若某一个子树大小大于$\sqrt{n}$ ,则直接背包。由于这样的子树不会超过$\sqrt{n}$ 个，因而复杂度为$O(n \sqrt{n})$.

另外小于$\sqrt{n}$ 的部分，对二进制进行拆分，复杂度为$O(nlogn)$.

因而总复杂度为$O(n \sqrt{n})$.

当然转移的部分可以用bitset来优化，复杂度为$O(\frac{n \sqrt{n}}{64})$.

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
#include<bitset>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=250001;
int head[N],tot_edge;
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[++tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge;
}
int n,son[N],mxson[N],heart;
void find_heart(int p,int f){
	son[p]=1;
	for(int i=head[p];i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		find_heart(to,p);	
		son[p]+=son[to];
		mxson[p]=max(mxson[p],son[to]);
	}
	mxson[p]=max(mxson[p],n-son[p]);
	if(!heart||mxson[heart]>mxson[p])heart=p;
}
int lim,cnt[505],num[505],tot;
ll ans1,ans2;
void dfs(int p,int f){
	son[p]=1;
	for(int i=head[p];i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		dfs(to,p);
		son[p]+=son[to];
	}
	if(heart==f){
		if(son[p]<=lim)cnt[son[p]]++;
		else num[++tot]=son[p];
	}
	ans1+=son[p]-1;
}
bitset<N>dp;
int main(){
	Rd(n);
	for(int i=1,a,b;i<n;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	find_heart(1,0);
	while(lim*lim<n)lim++;
	dfs(heart,0);
	dp[0]=1;
	while(tot)dp|=dp<<num[tot--];
	for(int i=1;i<=lim;i++){
		for(int j=cnt[i],k=1;j;j-=k,k<<=1){
			if(j<=k){
				dp|=dp<<(i*j);
				break;
			}else dp|=dp<<(i*k);
		}
	}
	for(int i=1;i<=n;i++)
		if(dp[i])ans2=max(ans2,1LL*(n-1-i)*i);
	printf("%d %lld\n",n-1,ans1+ans2);
	return 0;
}
分享到 评论