题目链接：https://qoj.ac/contest/1259/problem/6638
题目大意：给一棵以 $1$ 为根的树，举办一场投票，每个人只能向祖先投票，问每个点存不存在一种情况使得这个点的得票数严格大于其他点的得票数。（根不投票）
做法
考虑一个事情，一个子树大小为 $x$ 的点可以当选，那么显然一个子树大小 $y>x$ 的点也一定可以当选，但是 $y=x$ 呢？
显然如果子树大小为 $x$ 的点的形状不是菊花就行，如果是菊花的话就还得另外考虑。
于是我们就发现，答案结构应该是存在一个 $limit$ ，$siz>limit$ 一定可以，$siz=limit$ 得看情况（且必要条件是子树得是个菊花），考虑怎么找这个 limit ，显然得二分，但是怎么判断 $>mid$ 的子树全都可以呢？
观察上述结论的证明过程，发现关键在于对于一个点 $x$ ，子树大小为 $siz$ ，要求每个点的得票数 $<siz-1$ 时，这个子树能内部消化自己的得票数（也就是不是菊花），也就是说，存在一种情况使得整棵树的得票数的最大值 $<siz-1$ ，因此做法就出来了。
如果存在一个情况，使得整棵树的得票数最大值 $\le mid-1$ ，那么 $limit \le mid$ ，显然树形DP即可。
在找到 $limit$ 后，考虑处理 $siz=limit$ 的点，用树形 DP 跑一遍每个点的最大容量只有 $limit-2$ 的情况，显然，只有当根节点得票数为 $limit-1$ 且这个点的 $siz=limit$ 且这个点到根节点这条路径上一直存在 $dp$ 值的有效转移时，这个点才是可以当选的点，否则不符合这种情况。（显然，能符合上述要求的点，子树一定是个菊花，这也符合上面的讨论）
时间复杂度：$O(n\log{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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int p[N],siz[N],n;
void init(){
scanf("%d",&n);
memset(siz+1,0,sizeof(int)*n);
for(int i=2;i<=n;i++){
scanf("%d",&p[i]);
}
for(int i=n;i>=1;i--){
siz[i]+=1;
if(i!=1)siz[p[i]]+=siz[i];
}
}
int f[N];bool v[N];
int check(int U){
memset(f+1,0,sizeof(int)*n);
for(int i=n;i>=2;i--){
if(f[i]<=U)v[i]=0;
else v[i]=1;
f[p[i]]+=max(f[i]-U,0)+1;
}
return f[1]-U;
}
char ac[N];
void solve(){
init();
if(n==1){
printf("1\n");
return ;
}
int l=3,r=n+1,mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(check(mid-2)<=0)r=mid-1,ans=mid;
else l=mid+1;
}
for(int i=1;i<=n;i++){
if(siz[i]>=ans)ac[i]='1';
else ac[i]='0';
}
ac[1]='1';
if(ans!=2 && check(ans-3)==1){
v[1]=1;
for(int i=2;i<=n;i++){
if(v[p[i]] && v[i])v[i]=1;
else v[i]=0;
if(v[i] && siz[i]==ans-1)ac[i]='1';
}
}
ac[n+1]='\0';
printf("%s\n",ac+1);
}
int main(){
int T;scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
|
