自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 22:57:40，当前版本为作者最后更新于2024-05-05 22:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，假设将一个公司看成一个“大点”，则连接最后的“大树”每个点度数最多为 $2$，否则可以将一棵子树接到另一棵子树上，这样更优。

这里有两种情况：一是一条链，二是两条链通过一个公司连接在一起。

对于第一种情况，又有最顶是 $1$ 号树、最底是 $2$ 号树，和最顶是 $2$ 号树、最底是 $1$ 号树两种子情况。对于第一种子情况，选离 $x$ 最远的节点，接上另外一棵子树的根节点，产生 $dis(x,l)$ 的贡献（$l$ 是选中的叶子节点）；$3\sim n$ 只要接的都是距离最远的叶子节点就可以随便接；而 $2$ 子树会产生 $dis(1,y)$ 的贡献；再加上自己加的 $n-1$ 条边使其相连。第二种子情况类似，取个最大值即可。

对于第二种情况，枚举“大树”的根 $r$，这样在 $r$ 中的贡献会减去最大深度，加上最大叶子节点距离（类似树的直径的求法）。贪心取两者之差最大的。与第一种情况类似，但是还要加上 $dis(1,x)+dis(1,y)$。

讲的有点抽象，放个丑陋的代码：

int n,ans,mx1,mx2,mx3,x,y,d1[M],d2[M],mx[N],dmx[N]; vi G1[M],G2[M]; 
struct Tree {
	int m; vi dep,dep2; vector<vi> G;
	void dfs(int u,int fa=0) {for(int v:G[u]) if(v!=fa) dep[v]=dep[u]+1,dfs(v,u);}
	void rdfs(int u,int fa=0) {for(int v:G[u]) if(v!=fa) dep2[v]=dep2[u]+1,rdfs(v,u);}
}T[N];
void dfs1(int u,int fa=0) {for(int v:T[1].G[u]) if(v!=fa) {d1[v]=d1[u]+1; if(v!=1&&T[1].G[v].size()<=1) mx1=max(mx1,d1[v]); dfs1(v,u);}}
void dfs2(int u,int fa=0) {for(int v:T[2].G[u]) if(v!=fa) {d2[v]=d2[u]+1; if(v!=1&&T[2].G[v].size()<=1) mx2=max(mx2,d2[v]); dfs2(v,u);}}
void QwQ() {
	n=rd(),ans=n-1,mx3=-INF;
	for(int i=1;i<=n;i++) {
		T[i].m=rd(),T[i].G.resize(T[i].m+1),T[i].dep.resize(T[i].m+1),T[i].dep2.resize(T[i].m+1);
		for(int j=2,x;j<=T[i].m;j++) x=rd(),T[i].G[x].pb(j),T[i].G[j].pb(x);
	}
	x=rd(),y=rd(),dfs1(x),dfs2(y);
	for(int i=1,s;i<=n;i++) {
		T[i].dfs(1),s=-1;
		for(int j=2;j<=T[i].m;j++) if(T[i].dep[j]>=mx[i]&&T[i].G[j].size()==1) mx[i]=T[i].dep[j],s=j;
		if(i>2) ans+=mx[i];
		if(!~s) continue; T[i].rdfs(s);
		for(int j=2;j<=T[i].m;j++) if(T[i].G[j].size()==1) dmx[i]=max(dmx[i],T[i].dep2[j]);
	}
	for(int i=1;i<=n;i++) mx3=max(mx3,dmx[i]-mx[i]);
	wr(max(ans+max(d1[1]+mx2,d2[1]+mx1),mx3!=-INF?ans+mx3+d1[1]+d2[1]:0),"\n");
}