列表

详情

NC54640. [CSP2019]树的重心（centroid）

描述

已替换官方数据
小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：
  1. 一个大小为 n 的树由 n 个结点与 n − 1 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树
  2. 对于一个大小为 n 的树与任意一个树中结点 c，称 c 是该树的重心当且仅当在树中删去 c 及与它关联的边后，分裂出的所有子树的大小均不超过，（其中）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。
       课后老师给出了一个大小为 n 的树 S，树中结点从 1 ∼ n 编号。小简单的课后作业是求出 S 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：



        上式中， E 表示树 S 的边集， (u, v) 表示一条连接 u 号点和 v 号点的边。与分别表示树 S 删去边 (u, v) 后， u 号点与 v 号点所在的被分裂出的子树。
小简单觉得作业并不简单，只好向你求助，请你教教他。

输入描述

本题输入包含多组测试数据。
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 n 表示树 S 的大小。
接下来 n − 1 行，每行两个以空格分隔的整数 u_i, v_i，表示树中的一条边 (u_i, v_i)。

输出描述

共 T 行，每行一个整数，第 i 行的整数表示：第 i 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。

示例1

输入: 

2
5
1 2 
2 3 
2 4 
3 5 
7 
1 2 
1 3 
1 4 
3 5 
3 6 
6 7

输出: 

32
56

说明:

对于第一组数据：
删去边 (1, 2)， 1 号点所在子树重心编号为 {1}， 2 号点所在子树重心编号为 {2, 3}。
删去边 (2, 3)， 2 号点所在子树重心编号为 {2}， 3 号点所在子树重心编号为 {3, 5}。
删去边 (2, 4)， 2 号点所在子树重心编号为 {2, 3}， 4 号点所在子树重心编号为 {4}。
删去边 (3, 5)， 3 号点所在子树重心编号为 {2}， 5 号点所在子树重心编号为 {5}。
因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1580ms, 内存消耗: 23488K, 提交时间: 2019-11-21 20:41:20 

#include<bits/stdc++.h>
#define rep for(int s,i=lk[x];i;i=hd[i])\
if((s=to[i])^y)
const int N=300005;
using namespace std;
int T,n,sz[N],fl[N],fr[N],//from father [,]
ml[N],mr[N],//qry father [,]
to[N*2],hd[N*2],lk[N],cnt,
al[N],now[N],fa[N];//some fenwick trees fa:real fa size-fa size
long long ans;
inline void add(int u,int v){
	to[++cnt]=v,hd[cnt]=lk[u],lk[u]=cnt;
}int u,v;
inline void ins(int*a,int x,int v){
	for(x=max(x,1);x<=n;x+=x&-x)a[x]+=v;
}
inline int qry(int*a,int x){
	int y=0;
	for(;x;x-=x&-x)y+=a[x];
	return y;
}
void dfs(int x,int y){
	sz[x]=1;
	rep dfs(s,x),sz[x]+=sz[s];
	int mx=n-sz[x],se=0;
	rep{
		if(sz[s]>mx)se=mx,mx=sz[s];
		else if(sz[s]>se)se=sz[s];
	}
	rep fl[s]=2*sz[s]-n,fr[s]=n-2*(sz[s]==mx?se:mx);
	ml[x]=2*(n-sz[x])-n,mr[x]=n-2*(n-sz[x]==mx?se:mx);
	al[sz[x]]++;
}
inline void cr(int&x){
	if(x<0)x=0;
	if(x>n)x=n;
}
void dfss(int x,int y){
	fl[x]--,ml[x]--;
	cr(fl[x]),cr(fr[x]),cr(ml[x]),cr(mr[x]);
	if(fl[x]>fr[x])fl[x]=fr[x]=0;
	if(ml[x]>mr[x]||x==1)ml[x]=mr[x]=0;
	ans-=(qry(now,fr[x])-qry(now,fl[x]))*1ll*y;
	ans+=(al[mr[x]]-al[ml[x]]+qry(now,mr[x])-qry(now,ml[x])
	+qry(fa,mr[x])-qry(fa,ml[x]))*1ll*x;
	ins(now,sz[x],1);
	ins(fa,sz[x],-1);
	rep{
		ins(fa,n-sz[s],1);
		dfss(s,x);
		ins(fa,n-sz[s],-1);
	}
	ans+=(qry(now,fr[x])-qry(now,fl[x]))*1ll*y;
	ans-=(qry(now,mr[x])-qry(now,ml[x]))*1ll*x;
	ins(fa,sz[x],1);
}
int main(){
//	freopen("centroid.in","r",stdin);
//	freopen("centroid.out","w",stdout);
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		al[i]=now[i]=fa[i]=lk[i]=0;
		cnt=ans=0;
		//rem to clr
		for(int i=1;i<n;i++)
		scanf("%d%d",&u,&v),
		add(u,v),add(v,u);
		dfs(1,0);
		for(int i=1;i<=n;i++)
		al[i]+=al[i-1];
		dfss(1,0);
		//for(int i=1;i<=n;i++)
		//cerr<<i<<":["<<ml[i]<<','<<mr[i]<<"]\n"<<fqwq[i]<<'/'<<mqwq[i]<<endl;
		printf("%lld\n",ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 2649ms, 内存消耗: 51648K, 提交时间: 2019-11-24 09:45:22 

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int n,tot=1;
int head[N],nxt[N<<1],to[N<<1];
int sz[N],son[N],son2[N];
int f[N][20];
long long ans;
void dfs1(int x,int fa){
	sz[x]=1;
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa){
		dfs1(to[i],x);
		sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]]) son2[x]=son[x],son[x]=to[i];
		else if(sz[to[i]]>sz[son2[x]]) son2[x]=to[i];
	}
	f[x][0]=son[x];
	for(int i=1;i<=18;++i) f[x][i]=f[f[x][i-1]][i-1];
}
int solve(int x){
	if(!son[x]) return x;
	int now=x,ans=0;
	for(int i=18;~i;--i) if(sz[x]-sz[f[now][i]]<sz[x]/2) now=f[now][i];
	if(sz[son[now]]<=sz[x]/2&&sz[x]-sz[now]<=sz[x]/2) ans+=now;
	now=son[now];
	if(sz[son[now]]<=sz[x]/2&&sz[x]-sz[now]<=sz[x]/2) ans+=now;
	return ans;
}
void dfs2(int x,int fa){
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa){
		int tmp=son[x],s=sz[x];
		sz[x]=n-sz[to[i]];
		if(to[i]==son[x]) son[x]=son2[x];
		if(fa&&sz[fa]>sz[son[x]]) son[x]=fa;
		f[x][0]=son[x];
		for(int j=1;j<=18;++j) f[x][j]=f[f[x][j-1]][j-1];
		ans+=solve(to[i]);
		ans+=solve(x);
		dfs2(to[i],x);
		son[x]=tmp; sz[x]=s; f[x][0]=son[x];
		for(int j=1;j<=18;++j) f[x][j]=f[f[x][j-1]][j-1];
	}
}
inline void add(int a,int b){
	nxt[++tot]=head[a]; to[head[a]=tot]=b;
	nxt[++tot]=head[b]; to[head[b]=tot]=a;
}
inline int read(register int x=0,register char ch=getchar(),register int f=0){
	for(;!isdigit(ch);ch=getchar()) f=ch=='-';
	for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
int main(){
	int T=read();
	while(T--){
		tot=1; ans=0;
		memset(head,0,sizeof(head));
		memset(son,0,sizeof(son));
		memset(son2,0,sizeof(son2));
		n=read();
		for(int i=1;i<n;++i) add(read(),read());
		dfs1(1,0); dfs2(1,0);
		printf("%lld\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com