P4183 [USACO18JAN]Cow at Large P

P4183 [USACO18JAN]Cow at Large P

原题传送门:>Here<

我们先考虑只求一个点时怎么做。

设$f_i$为$i$到叶结点的最短距离。

假设我们在处理$root$的答案。可以发现,

当$dis_{root,i}\ge f_i$时,$i$的子树只需要放一个人就可以“封锁”。

可以发现满足这个条件的点构成很多棵子树,而我们的答案就是子树的个数。

现在我们考虑怎么得到子树个数。

设$val_i=2-d_i$,其中$d_i$表示点$i$的度数。

我们可以发现,一棵子树的权值和正好等于$1$。

考虑为什么是这样。

设一棵子树中有$x$个点,那么有$x-1$条在子树内的边。所以贡献即为$2*x-2(x-1)=2$。因为我们求的是“子树”权值和,所以必有一条连出去的边。这样贡献即为$2-1=1$。

所以我们只要对于$dis_{i,j}\ge f_j$,将$ans_i$加上$2-d_j$即可。

这样复杂度是$O(n^2)$的。

考虑点分治。则对于$i$,满足条件的$j$满足$dis_i+dis_j\ge f_j$。

移项一下,得到$dis_i\ge f_j-dis_j$。后面那个东西用树状数组维护一下即可。

代码:

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
using namespace std;

int d[70001],head[70001],nxt[140001],b[140001],k,n,ml[70001],size[70001],full,root,mx[70001],stk[70001],top,ans[70001];
bool vis[70001];
void push(int s,int t){
nxt[++k]=head[s];
head[s]=k;
b[k]=t;
++d[t];
}
void dfs1(int x,int f){
if(d[x]==1)ml[x]=0;
else ml[x]=n+1;
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f){
dfs1(b[i],x);
ml[x]=min(ml[x],ml[b[i]]+1);
}
}
void dfs2(int x,int f){
if(f)ml[x]=min(ml[x],ml[f]+1);
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f)dfs2(b[i],x);
}
void getroot(int x,int f){
size[x]=1;
mx[x]=0;
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f&&!vis[b[i]]){
getroot(b[i],x);
mx[x]=max(mx[x],size[b[i]]);
size[x]+=size[b[i]];
}
mx[x]=max(mx[x],full-size[x]);
if(mx[x]<mx[root])root=x;
}
int c[70001];
void update(int ind,int num){++ind;for(;ind<=n;ind+=ind&-ind)c[ind]+=num;}
int query(int ind){++ind;int tot=0;for(;ind>0;ind-=ind&-ind)tot+=c[ind];return tot;}
void getans(int x,int f,int dis){
ans[x]+=query(dis);
// printf("get %d %d %d\n",x,dis,ans[x]);
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f&&!vis[b[i]])
getans(b[i],x,dis+1);
}
void setans(int x,int f,int dis,int delta){
// printf("set %d %d %d\n",x,ml[x]-dis,delta*(2-d[x]));
update(max(ml[x]-dis,0),delta*(2-d[x]));
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f&&!vis[b[i]])
setans(b[i],x,dis+1,delta);
}
void getsize(int x,int f){
++full;
for(int i=head[x];i;i=nxt[i])
if(b[i]!=f&&!vis[b[i]])
getsize(b[i],x);
}
void solve(int rt){
vis[rt]=1;
for(int i=head[rt];i;i=nxt[i])
if(!vis[b[i]])getans(b[i],rt,1),setans(b[i],rt,1,1),stk[++top]=b[i];
//printf("*--> %d %d %d\n",rt,query(0),ans[rt]);
ans[rt]+=query(0);
for(int i=top;i;i--)setans(stk[i],rt,1,-1);
update(ml[rt],2-d[rt]);
for(int i=top;i;i--)getans(stk[i],rt,1),setans(stk[i],rt,1,1);
while(top)setans(stk[top],rt,1,-1),--top;
update(ml[rt],d[rt]-2);
for(int i=head[rt];i;i=nxt[i])
if(!vis[b[i]]){
full=0;
getsize(b[i],rt);
mx[root=0]=full;
getroot(b[i],rt);
//printf("%d %d %d %d\n",rt,b[i],root,top);
solve(root);
}
}
int main(){
scanf("%d",&n);
for(int i=1,s,t;i<n;i++){
scanf("%d%d",&s,&t);
push(s,t);
push(t,s);
}
dfs1(1,0);
dfs2(1,0);
// for(int i=1;i<=n;i++)printf("%d ",d[i]);
// putchar('\n');
full=n,mx[root=0]=full;
getroot(1,0);
solve(root);
for(int i=1;i<=n;i++){
if(d[i]!=1)printf("%d\n",ans[i]);
else puts("1");
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×