洛谷 P4183 - [USACO18JAN]Cow at Large P（點分治）

點分治好題

洛谷題面傳送門

點分治 hot tea。

首先考慮什麼樣的點能夠對以 \(u\) 為根的答案産生 \(1\) 的貢獻。我們考慮以 \(u\) 為根對整棵樹進行一遍 DFS。那麼對于一個點 \(v\)，我們記其 \(mn_v\) 為其子樹内距離其最近的葉子，\(dep_v\) 為 \(u\) 到 \(v\) 的距離，那麼如果 \(mn_v\ge dep_v\)，那麼對于任何一個 \(v\) 子樹内的葉子 \(w\)，如果 Bessie 選擇從 \(w\) 逃出且我們在距離 \(v\) 最近的葉子處放上一個看守者，那麼在 \(v\) 處的看守者必然能夠在 Bessie 到達 \(w\) 之前把 Bessie 截住。并且根據貪心的原理，隻有當如果 \(v\) 的父親 \(fa_v\) 不符合 \(mn_{fa_v}\ge dep_{fa_v}\) 時我們才會選擇在距離 \(v\)​ 最近的葉子，并且這樣的點必須被選，否則 \(v\) 子樹内的點就堵不住了。是以一個點 \(v\) 産生條件的必要條件是 \(mn_v\ge dep_v\land mn_{fa_v}<dep_{fa_v}\)。那這是否充分了呢？或者說是否會存在某個葉子，滿足兩個産生貢獻的點都選到這個點。答案是否定的，因為如果存在兩個點 \(v_1,v_2\)，滿足距離它們最近的葉子相同，并且 \(mn_{v_1}\ge dep_{v_1},mn_{v_2}\ge dep_{v_2}\) 均成立，那麼必然有它們的 LCA 也符合要求。是以對于一個 \(u\)，滿足條件的 \(v\) 的個數就是

\[\sum\limits_{v}[mn_v\ge\text{dis}(v,u)][mn_{fa_v}<\text{dis}(fa_v,u)]

\]

注意到這裡涉及兩個次元，如果硬要上個點分治那需要三位偏序，非常麻煩。不過注意到對于一個點，如果其滿足第一個限制，那麼它的子樹也滿足這個限制。那麼怎樣讓每個子樹的貢獻都隻算一次呢？考慮一個大小為 \(x\) 的子樹 \(S\)，由于該子樹中深度最淺的節點上面還連了條邊，是以該節點中所有點的度 \(d_v\) 之和等于 \(2x-1\)​，移個項可得 \(\sum\limits_{v\in S}2-d_v=1\)，是以上式等價于

\[\sum\limits_{v}(2-d_v)·[mn_v\ge\text{dis}(v,u)]

const int MAXN=7e4;
const int INF=0x3f3f3f3f;
int n,deg[MAXN+5],hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int mx[MAXN+5],cent=0,siz[MAXN+5];bool vis[MAXN+5];
int mndep[MAXN+5],mnout[MAXN+5],mn[MAXN+5];
void dfs1(int x,int f){
	mndep[x]=(deg[x]==1)?0:INF;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		dfs1(y,x);chkmin(mndep[x],mndep[y]+1);
	}
}
void dfs2(int x,int f){
	multiset<int> st;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];
		if(y==f) st.insert(mnout[x]);
		else st.insert(mndep[y]+1);
	}
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f) continue;
		if(deg[x]==1) mnout[y]=1;
		else{
			st.erase(st.find(mndep[y]+1));
			mnout[y]=(*st.begin())+1;
			st.insert(mndep[y]+1);
		} dfs2(y,x);
	}
}
void findcent(int x,int f,int tot){
	siz[x]=1;mx[x]=0;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f||vis[y]) continue;
		findcent(y,x,tot);siz[x]+=siz[y];chkmax(mx[x],siz[y]);
	} chkmax(mx[x],tot-siz[x]);
	if(mx[x]<mx[cent]) cent=x;
}
int dep[MAXN+5];
void getdep(int x,int f){
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(vis[y]||y==f) continue;
		dep[y]=dep[x]+1;getdep(y,x);
	}
}
ll t[MAXN*2+5],res[MAXN+5];
void add(int x,int v){x+=n+1;for(int i=x;i<=(n<<1|1);i+=(i&(-i))) t[i]+=v;}
ll query(int x){x+=n+1;ll ret=0;for(int i=x;i;i&=(i-1)) ret+=t[i];return ret;}
vector<int> pt;
void getpts(int x,int f){
	pt.pb(x);
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(vis[y]||y==f) continue;
		getpts(y,x);
	}
}
void divcent(int x){
//	printf("divcent %d\n",x);
	vis[x]=1;dep[x]=0;vector<int> tot;tot.pb(x);
	add(mn[x]-dep[x],2-deg[x]);stack<int> stk;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(vis[y]) continue;
		dep[y]=1;getdep(y,x);stk.push(y);
		pt.clear();getpts(y,x);
		for(int p:pt) res[p]+=query(dep[p]);
		for(int p:pt) add(mn[p]-dep[p],2-deg[p]),tot.pb(p);
	} for(int y:tot) add(mn[y]-dep[y],deg[y]-2);
	tot.clear();
	while(!stk.empty()){
		int y=stk.top();stk.pop();
		pt.clear();getpts(y,x);
		for(int p:pt) res[p]+=query(dep[p]);
		for(int p:pt) add(mn[p]-dep[p],2-deg[p]),tot.pb(p);
	} res[x]+=query(dep[x]);
	for(int y:tot) add(mn[y]-dep[y],deg[y]-2);
	tot.clear();
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(vis[y]) continue;
		cent=0;findcent(y,x,siz[y]);divcent(cent);
	}
}
int main(){
//	freopen("P4183_7.in","r",stdin);
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		adde(u,v);adde(v,u);deg[u]++;deg[v]++;
	} dfs1(1,0);mnout[1]=INF;dfs2(1,0);
	for(int i=1;i<=n;i++) mn[i]=min(mndep[i],mnout[i]);
//	for(int i=1;i<=n;i++) printf("%d %d %d\n",mn[i],mndep[i],mnout[i]);
	mx[0]=INF;findcent(1,0,n);divcent(cent);
	for(int i=1;i<=n;i++) printf("%lld\n",res[i]);
	return 0;
}