luogu P4183 [USACO18JAN]Cow at Large P

题面传送门

奇妙的题目。

首先我们可以得出当\(u\)点为根的时候\(i\)点是否可以被控制：设\(g_i\)表示\(i\)号点到最近的叶子距离，则当$g_i\geq dist(u,i) \(时\)u\(子树内的点可以在牛到这个点之前爬到这个点。如果这个点最终停了一个点，则这个点还需要满足\)g_{fa_i}<dist(u,fa_i)\(。因此我们得到一个\)O(n^2)$的方法。

这个限制不是很好做，容易发现如果一个点1满足限制则整个子树的点都满足限制，又有\(\sum\limits_{i\in subtree_i}{deg_i}=2|subtree_i|-1\)，有\(1=\sum\limits_{i\in subtree_i}{2-deg_i}\)。故可以转化成点对贡献，直接点分治即可。

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=7e4+5,M=pow(6,10)+5,K=2e3+5,mod=998244353,Mod=mod-1;const db eps=1e-5;const int INF=1e9+7;
int n,m,k,x,y,z,In[N],g[N],Ans[N];vector<int> S[N];
void BFS(){
	int i;queue<int> Q;while(!Q.empty()) Q.pop();Me(g,-1);for(i=1;i<=n;i++) if(In[i]==1) Q.push(i),g[i]=0;
	while(!Q.empty()) {int x=Q.front();Q.pop();for(int i:S[x]) g[i]==-1&&(Q.push(i),g[i]=g[x]+1);}
}
namespace Tree{int f[N*2];void Ins(int x,int y){while(x<=2*n) f[x]+=y,x+=x&-x;}int Qry(int x){int Ans=0;while(x) Ans+=f[x],x-=x&-x;return Ans;}}
namespace PC{
	int dp[N],Si[N],Ct,vis[N],Rt,d[N];
	void GI(int x,int La){Ct++;for(int i:S[x]) i^La&&!vis[i]&&(GI(i,x),0);}
	void DP(int x,int La){Si[x]=1;dp[x]=0;for(int i:S[x]) i^La&&!vis[i]&&(DP(i,x),Si[x]+=Si[i],dp[x]=max(dp[x],Si[i]));dp[x]=max(dp[x],Ct-Si[x]);dp[x]<dp[Rt]&&(Rt=x);}
	void Make(int x,int La){d[x]=d[La]+1;for(int i:S[x]) i^La&&!vis[i]&&(Make(i,x),0);}
	void Ins(int x,int La,int op){Tree::Ins(g[x]-d[x]+n,op*(2-In[x]));for(int i:S[x]) i^La&&!vis[i]&&(Ins(i,x,op),0);}
	void Qry(int x,int La){Ans[x]+=Tree::Qry(d[x]+n);for(int i:S[x]) !vis[i]&&i^La&&(Qry(i,x),0);}
	void dfs(int x,int La){
		Ct=0;GI(x,La);Rt=0;DP(x,La);x=Rt;vis[x]=1;Tree::Ins(g[x]+n,2-In[x]);
		d[x]=0;for(int i:S[x]) !vis[i]&&(Make(i,x),Ins(i,x,1),0);
		for(int i:S[x]) !vis[i]&&(Ins(i,x,-1),Qry(i,x),Ins(i,x,1),0);Tree::Ins(g[x]+n,In[x]-2);Ans[x]+=Tree::Qry(n);
		for(int i:S[x]) !vis[i]&&(Ins(i,x,-1),0);
		for(int i:S[x]) !vis[i]&&(dfs(i,x),0);
	}
}
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	int i,j;scanf("%d",&n);for(i=1;i<n;i++) scanf("%d%d",&x,&y),In[x]++,In[y]++,S[x].PB(y),S[y].PB(x);BFS();
	PC::dp[0]=1e9;PC::dfs(1,0);for(i=1;i<=n;i++) printf("%d\n",Ans[i]); 
}