题目描述

n<=7e4

题解

先考虑只求根答案怎么办

鱼从根向下走，风从叶子向上走直到相遇，最后风经过的点合起来的树个数就是答案（每棵树只需要放一个风即可）

形式化一下，设f[i]表示i距最近的叶子的距离，则风会经过i当且仅当dis(root,i)>=f[i]，即风先一步or同时到达i

考虑怎么统计子树

子树的性质：度数和=2点数-1

证明：内部的边为点数-1，加上顶端的单向出边就是 2点数-1

所以\(\sum 2-deg=1\)，用点分治维护2-deg即可

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define low(x) ((x)&-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define inf 2133333333
#define ll long long
#define file
using namespace std;

int tr[140002],D[140002],a[140001][2],ls[70001],size[70001],f[70001],d[70001],ans[70001],n,i,j,k,l,len,mn,Mn,tot,N;
bool bz[70001],Bz[140002];

void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
void dfs(int Fa,int t)
{
	int i;
	f[t]=(d[t]==1)?0:inf;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	{
		dfs(t,a[i][0]);
		f[t]=min(f[t],f[a[i][0]]+1);
	}
}
void Dfs(int Fa,int t,int F)
{
	int i,mn=inf,mn2=inf,Mn=-1;
	f[t]=min(f[t],F+1);
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	{
		if (f[a[i][0]]<mn)
		mn2=mn,mn=f[a[i][0]],Mn=a[i][0];
		else
		if (f[a[i][0]]<mn2)
		mn2=f[a[i][0]];
	}
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	{
		if (d[t]==1) {Dfs(t,a[i][0],0);continue;}
		if (a[i][0]==Mn)
		Dfs(t,a[i][0],min(F,mn2)+1);
		else
		Dfs(t,a[i][0],min(F,mn)+1);
	}
}

void change(int t,int s) {if (!s) return;while (t<=n+n+1) {tr[t]+=s;if (!Bz[t]) Bz[t]=1,D[++tot]=t;t+=low(t);}}
int find(int t) {int ans=0; while (t) ans+=tr[t],t-=low(t); return ans;}

void dfs1(int Fa,int t)
{
	int i,mx=0;
	size[t]=1;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && !bz[a[i][0]])
	{
		dfs1(t,a[i][0]);
		size[t]+=size[a[i][0]];
		mx=max(mx,size[a[i][0]]);
	}
}
void Dfs1(int Fa,int t)
{
	int i,mx=0;
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && !bz[a[i][0]])
	{
		Dfs1(t,a[i][0]);
		mx=max(mx,size[a[i][0]]);
	}
	if (max(mx,N-size[t])<mn)
	mn=max(mx,N-size[t]),Mn=t;
}
void dfs2(int T,int Fa,int t,int dp,int s)
{
	int i;
	change(f[t]-dp+n+1,s*(2-d[t]));
	if (T && t!=T && dp>=f[t]) ans[T]+=2-d[t];
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && !bz[a[i][0]])
	dfs2(T,t,a[i][0],dp+1,s);
}
void dfs3(int T,int Fa,int t,int dp)
{
	int i;
	ans[t]+=find(dp+n+1);
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && !bz[a[i][0]])
	dfs3(T,t,a[i][0],dp+1);
}

void work(int t)
{
	int i;
	
	mn=inf;
	dfs1(0,t);
	N=size[t];
	Dfs1(0,t);
	
	t=Mn;tot=0;
	if (t==3)
	n=n;
	dfs2(t,0,t,0,1);
	if (tot)
	{
		for (i=ls[t]; i; i=a[i][1])
		if (!bz[a[i][0]])
		{
			dfs2(0,t,a[i][0],1,-1);
			dfs3(0,t,a[i][0],1);
			dfs2(0,t,a[i][0],1,1);
		}
		fo(i,1,tot) Bz[D[i]]=tr[D[i]]=0;
	}
	
	bz[t]=1;
	for (i=ls[t]; i; i=a[i][1])
	if (!bz[a[i][0]])
	work(a[i][0]);
}

int main()
{
//	freopen("d.in","r",stdin);
//	#ifdef file
//	freopen("b.out","w",stdout);
//	#endif
	
	scanf("%d",&n);
	fo(i,1,n-1) scanf("%d%d",&j,&k),New(j,k),New(k,j),++d[j],++d[k];
	
	dfs(0,1);
	Dfs(0,1,inf);
	work(1);
	
	fo(i,1,n) printf("%d\n",(d[i]==1)?1:ans[i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

100130. 鱼池逃脱Cow at Large（子树性质）

原文：https://www.cnblogs.com/gmh77/p/12827829.html