自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:35:06，当前版本为作者最后更新于2022-01-02 23:13:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

stO sgygd Orz

这是一个我自己编的做法，不知道和 std 是否一样。

乍一看这道题的传送门和一大堆奇怪的限制一点思路都没有。

我们先来分析一下建立一对传送门实际上会发生什么。

可以发现，在 $(u_1,v_1)$ 上和 $(u_2,v_2)$ 上建立一对传送门相当于断开 $(u_1,v_1)$ 和 $(u_2,v_2)$，并连接 $(u_1,u_2)$ 和 $(v_2,v_2)$。

显然上面的操作不会改变每个点的度数，并且弱于每次交换两个点的父亲。由于题目要求最终每个点都要能够到达，所以最终状态也必须是一棵树。

注意：这里交换两个点的父亲可能会在过程中产生环，但这并不重要，只要保证最终是一棵树即可。

显然如果新树中每个点的度数都与原树一样，那么一定可以达到这个状态。

现在我们的目标就是使得新树中所有关键点的深度之和最小。

先考虑一个暴力做法。

把所有的点（除了根节点）按照度数从大到小排序。如果某个关键点与非关键点度数一样，那么关键点排在前面。

我们需要考虑的是新树中所有关键点和根节点形成的虚树。

显然虚树中所有非关键节点一定处于一个前缀中（也就是尽量大），否则肯定不优。

我们枚举这个前缀，然后贪心地把所有虚树中的节点按照度数从大到小依次加入，每次选择一个深度最浅的还没连满的点连上去。这样一定是最优的（感性理解）。

注意：如果有至少一个点不在虚树中，则需要保证连完之后至少还剩一个点没有连满，否则就不合法了。

至此我们就得到了一个 $O(n^2)$ 做法。

那么如何优化它呢？

我们把每次加入一个节点改为每次加入一层节点。

如果当前加入的这一层的所有点度数都 $\ge 2$，那么这一层的度数总和至少是上一层的 $2$ 倍。

而所有点的度数和是 $O(n)$ 的，也就是说，这样的层数不会超过 $O(\log n)$！

在枚举完所有这样的层之后，剩下的点的度数就都 $\le 1$ 了，可以直接 $O(1)$ 特判掉。

利用这种做法就可以 $O(\log n)$ 地算出某一个前缀的答案。构造方案时只需要记录答案最优的前缀，然后再 $O(n)$ 模拟一遍之前的做法即可。

时间复杂度 $O(n\log n)$。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define LIM 1000005
#define ll long long
#define pb push_back
#define gc() (P1==P2 && (P2=(P1=buf)+fread(buf,1,LIM,stdin),P1==P2)?EOF:*P1++)
const ll INF=1e18;char *P1,*P2,buf[LIM];
int T,n,m,c,nw,tmp,cnt,dg[N],fa[N],fe[N],fa1[N],z[N],z1[N],s[N],q[N];ll w,res,ans1;
bool tg[N],tg1[N];set<int> ps[N];struct Edge {int v,id;};vector<Edge> e[N];
struct Node {int x;bool tg;};vector<Node> ans[N];
int rd()
{
	int res=0;char c=0;while(!isdigit(c)) c=gc();
	while(isdigit(c)) res=res*10+c-48,c=gc();return res;
}
void print(int x) {if(x<10) {putchar(x+48);return;}print(x/10);putchar(x%10+48);return;}
bool cmp(int x,int y) {return dg[x]*2+tg1[x]==dg[y]*2+tg1[y]?x<y:dg[x]*2+tg1[x]<dg[y]*2+tg1[y];}
void f(int u,int v) {++nw;ans[fe[u]].pb((Node) {nw,tg[u]});ans[fe[v]].pb((Node) {nw,!tg[v]});}
void dfs(int u,int f)
{fa[u]=f;for(auto i:e[u]) if(i.v!=f) tg[i.v]=i.id<0,fe[i.v]=abs(i.id),++dg[u],dfs(i.v,u);}
ll slv1(int x,int d,int w1,int w2)
{
	int t;ll res=0;if(x<=w1) {return x<w1 || s[x]?1ll*x*d:INF;}
	res=1ll*w1*d;++d;x-=w1;w2+=s[x+w1]-s[x];if(!w2) return INF;
	while(1)
	{
		if(x<=w2) {return x<w2 || s[x]?res+1ll*x*d:INF;}
		res+=1ll*w2*d;++d;x-=w2;w2=s[x+w2]-s[x];if(dg[z1[x]]<2) break;
	}if(min(x,cnt)>=w2) return INF;t=x/w2;return res+1ll*(d*2+t-1)*t*w2/2+1ll*(d+t)*(x%w2);
}
void slv()
{
	n=rd();m=rd();c=rd();if(n==1) {puts("0");return;}nw=cnt=w=0;q[0]=2;q[1]=1;
	for(int i=1;i<=n;++i) dg[i]=fa1[i]=tg1[i]=0,z[i]=i,ps[i].clear(),e[i].clear(),ans[i].clear();
	for(int i=1,u,v;i<n;++i) u=rd(),v=rd(),e[u].pb((Edge) {v,i}),e[v].pb((Edge) {u,-i});
	for(int i=1;i<=m;++i) z1[i]=rd(),tg1[z1[i]]=1;dfs(1,0);
	
	sort(z+2,z+n+1,cmp);sort(z1+1,z1+m+1,cmp);for(int i=1;i<=m;++i) s[i]=s[i-1]+dg[z1[i]];
	for(int i=1;i<=m;++i) if(!dg[z1[i]]) ++cnt;tmp=n+1;ans1=slv1(m,1,dg[1],0);
	for(int i=n,t=m,d=1,w1=dg[1],w2=0;i>1;--i)
	{
		if(tg1[z[i]]) --t,w+=d;--w1;w2+=dg[z[i]];if(!w1) ++d,swap(w1,w2);
		res=w+(i>2?slv1(t,d,w1,w2):0);if(res<ans1) tmp=i,ans1=res;
	}for(int i=1;i<=dg[1];++i) q[++q[1]]=1;
	for(int i=n;i>1;--i) if(i>=tmp || tg1[z[i]])
	{fa1[z[i]]=q[q[0]++];for(int j=1;j<=dg[z[i]];++j) q[++q[1]]=z[i];}
	for(int i=n;i>1;--i) if(!fa1[z[i]])
	{fa1[z[i]]=q[q[0]++];for(int j=1;j<=dg[z[i]];++j) q[++q[1]]=z[i];}
	
	printf("%lld\n",ans1);for(int i=2;i<=n;++i) ps[fa[i]].insert(i);
	for(int i=2,t;i<=n;++i) if(fa[i]!=fa1[i])
	{
		t=*ps[fa1[i]].begin();ps[fa[i]].erase(i);
		f(i,t);ps[fa[t]].erase(t);ps[fa[i]].insert(t);swap(fa[i],fa[t]);
	}else ps[fa[i]].erase(i);
	for(int i=2;i<=n;++i) if(tg[i]) reverse(ans[fe[i]].begin(),ans[fe[i]].end());
	for(int i=1;i<n;++i)
	{
		print(ans[i].size());putchar(' ');
		for(auto j:ans[i]) print(j.x),putchar(' '),print(j.tg),putchar(' ');puts("");
	}
}
int main() {T=rd();while(T--) slv();return 0;}