题解 P4183 【[USACO18JAN]Cow at Large P】
y2823774827y
2019-03-01 11:56:16
~~感觉楼下写的有点不清楚，反正我看不懂，这么说dalao是不是有点不好~~
显然，$g_i$为$i$到最近叶子节点的距离，$d_i$为$i$的度数
假设我们要求的是$ans_u$，如果把$u$作为根，$dep_i≥g_i$则$i$这棵子树贡献为$1$就能拦截$u$，但为了保证唯一性，$dep_i≥g_i \&\& dep_{fa_{i}}<g_{fa_{i}}$
时间复杂度$O(n^2)$
点对贡献，考虑用点分治优化
对于一棵**子树**，$\sum\limits^m d_i=2m-1,\therefore 1=\sum\limits^m (2-d_i)$，根据子树贡献单调性，$ans_u=\sum\limits_{i=1}^n [dis(u,i)≥g_i](2-d_i)$
至此，该题转换成点分治模板题，时间复杂度$O(nlog^2n)$
乱七八糟的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=1e5,inf=0x3f3f3f3f;
struct node{
LL to,nxt;
}dis[maxn<<1];
LL n,root,num,up,N,mi,tim;
LL ans[maxn],head[maxn],d[maxn],g[maxn],tree[maxn],visit[maxn],size[maxn],V[maxn];
inline void Add(LL u,LL v){
dis[++num]=(node){v,head[u]}, head[u]=num;
++d[v];
}
void Dfs1(LL u,LL f){
if(d[u]==1) g[u]=0;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(v==f) continue;
Dfs1(v,u);
g[u]=min(g[u],g[v]+1);
}
}
void Dfs2(LL u,LL f){
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(v==f) continue;
g[v]=min(g[v],g[u]+1);
Dfs2(v,u);
}
}
inline LL Lowbit(LL x){ return x&-x; }
inline LL Query(LL x){ LL ret(0); x+=up; for(;x;x-=Lowbit(x)) ret+=tree[x]; return ret; }
inline void Modify(LL x,LL val){ x+=up; for(;x<=100000;x+=Lowbit(x)) tree[x]+=val; }
void Dfs(LL u){
LL mx(0); visit[u]=true; size[u]=1;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Dfs(v); size[u]+=size[v];
mx=max(mx,size[v]);
}mx=max(mx,N-size[u]);
if(mi>mx) mi=mx,root=u;
visit[u]=false;
}
void Get(LL u,LL dt){
ans[u]+=Query(dt);
visit[u]=true;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Get(v,dt+1);
}visit[u]=false;
}
void Up(LL u,LL dt){
Modify(g[u]-dt,2-d[u]);
visit[u]=true;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Up(v,dt+1);
}visit[u]=false;
}
void Clear(LL u,LL dt){
Modify(g[u]-dt,-(2-d[u]));
visit[u]=true;
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Clear(v,dt+1);
}visit[u]=false;
}
void Div(LL u){
mi=inf, Dfs(u);
u=root;
visit[u]=true;
LL top(0);
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
V[++top]=v;
Get(v,1);
Up(v,1);
}
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Clear(v,1);
}
Modify(g[u],2-d[u]);
for(LL i=top;i>=1;--i){
LL v(V[i]);
Get(v,1);
Up(v,1);
}ans[u]+=Query(0);
Modify(g[u],-(2-d[u]));
for(LL i=head[u];i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
Clear(v,1);
}
for(LL i=head[u],sum=N;i;i=dis[i].nxt){
LL v(dis[i].to);
if(visit[v]) continue;
N=(size[v]>size[u]?sum-size[u]:size[v]);
Div(v);
}
}
int main(){
cin>>n; up=n;
for(LL i=1;i<n;++i){
LL u,v; cin>>u>>v;
Add(u,v), Add(v,u);
}
memset(g,inf,sizeof(g));
Dfs1(1,0), Dfs2(1,0);
N=n; Div(1);
for(LL i=1;i<=n;++i) if(d[i]==1) cout<<1<<endl;else cout<<ans[i]<<endl;
return 0;
}
```