洛谷 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)]
\]

这东西就一脸可以点分治的样子了，考虑对于一个 \(u\) 以及一个与其不在一个分治中心儿子子树内的点 \(v\)，那么记 \(dep_u\) 为 \(u\) 到分治中心的距离，那么限制可转化为 \(mn_v\ge dep_u+dep_v\)，移个项可得 \(mn_v-dep_v\ge dep_u\)，BIT 维护即可，时间复杂度 \(n\log^2n\)。

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;

}

巴特西

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

最新文章

热门文章