题解：P8004 Welcome to Lunatic City
WaTleZero_pt
·
·
题解
有一种通过亿些分析和证明得到了一种非常厉害的 $O(n)$ 做法但我太菜了并没有听懂，所以来写一下另一位同学提出的相对简单的 $O(n \log n)$ 做法（那位同学似乎分析有误把自己做法的复杂度当成了 $O(n \sqrt n)$？）。
首先考虑建传送门的本质是什么。如果在两条边 $(u_{1},v_{1})$ 和 $(u_{2},v_{2})$ 之间各添加一个同类的传送门并且方向相同，那么效果等同于切断边 $(u_{1},v_{1})$ 和 $(u_{2},v_{2})$ 并连接两条新边 $(u_{1},u_{2})$ 和 $(v_{1},v_{2})$。那么很显然，通过这样的操作，我们可以任意重连树边，但是不能改变每个点的度数。
因此，为了尽可能减少关键点到点 $1$ 的距离之和，我们可以想到一个非常简易的贪心，那就是将点 $2 \sim n$ 以度数为第一关键字，是否为关键点为第二关键字进行排序，然后依次挂到树上最浅的位置。但是很遗憾，这个做法只能通过子任务 $2$。因为我们只需要尽量把关键点往比较浅的位置挂，有些非关键点可以“让出来”放到很深的位置给关键点让位置。
那么，我们尝试换一种贪心思路。仍然按照原方法排序，但是现在我们每次枚举一段前缀并按照原方法做前缀，后面的部分改为以是否为关键点为第一关键字，度数为第二关键字进行排序，再继续按照原方法把这些点挂到树上，这样我们既通过前缀的那些点留出了足够多的空位放关键点，又能及时把关键点尽可能往上放，于是暴力实现我们就有了 $O(n^2)$ 解法。
这个复杂度还是难以接受，但显然我们有优化的方法。容易发现当剩余的点度数不超过 $2$ 的时候我们只能像扫把一样把这些点挂成一条条链，这是容易快速计算结果的；而度数不小于 $3$ 的时候显然每一层点的个数都至少是上一层的 $2$ 倍，因此这种情况不超过 $O(\log n)$ 层，所以我们就可以做到 $O(\log n)$ 计算每一个前缀的答案了。
可能有一些细节需要处理，比如 $1$ 度点堵住了所有空隙使得剩余的非关键点无处可放这种情况不能考虑，还有别忘了 $n=1$ 要特判。
::::success[AC Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=100010;
int n,m,l,u,v;
vector<pii> g[N];
int ans[N][2];
struct Node{
int deg,id,imp;
bool operator>(const Node &x)const{return deg==x.deg?imp>x.imp:deg>x.deg;}
}a[N];
struct Edge{
int u,v;
}e[N];
int lis[N],len,pre[N],opre[N];
void init(){
for(int i=1;i<=n;i++){
a[i]=(Node){0,i,0};
g[i].clear();
}
len=0;
}
void work(){
scanf("%d%d%d",&n,&m,&l);
if(n==1){
printf("0\n");
return;
}
init();
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
e[i].u=u; e[i].v=v;
g[u].emplace_back(i,0);
g[v].emplace_back(i,1);
a[u].deg++; a[v].deg++;
}
for(int i=1;i<=m;i++){
scanf("%d",&u);
a[u].imp=1;
}
sort(a+2,a+n+1,greater<Node>());
int onedeg=0;
for(int i=n;i>=2;i--){
if(a[i].imp){
lis[++len]=i;
pre[len]=pre[len-1]+a[i].deg-1;
opre[len]=opre[len-1]+(a[i].deg==1);
if(a[i].deg==1) onedeg++;
}
}
int dep=1,rem=a[1].deg,nxt=0,cur,tdep,trem,tnxt,use,id=0,uone;
ll nowans=0,tans,mnans=LLONG_MAX;
for(int i=1;i<=n;i++){
if(i>1){
rem--; nxt+=a[i].deg-1;
if(a[i].imp){
nowans+=dep;
if(a[i].deg==1) onedeg--;
len--;
}
if(rem==0) rem=nxt,nxt=0,dep++;
}
cur=len,tdep=dep,trem=rem,tnxt=nxt,use=0,tans=nowans,uone=0;
while(cur){
use=min(trem,cur);
tans+=tdep*(ll)use;
tnxt+=pre[cur]-pre[cur-use];
uone+=opre[cur]-opre[cur-use];
cur-=use; trem=tnxt; tnxt=0; tdep++;
if(a[lis[cur]].deg<=2) break;
}
if(cur){
if(!trem) continue;
int turn=cur/trem; cur%=trem;
tans+=trem*(ll)(tdep+tdep+turn-1)*turn/2;
tans+=cur*(ll)(tdep+turn);
}
if(len+i!=n&&onedeg-uone>=trem) continue;
if(tans<mnans){
id=i;
mnans=tans;
}
}
queue<pii> elis;
for(pii p:g[1]) elis.push(p);
int tcnt=0;
for(int i=2;i<=id;i++){
pii ea=elis.front(),eb=g[a[i].id].back();
elis.pop(); g[a[i].id].pop_back();
ans[ea.first][ea.second]=ans[eb.first][eb.second]=++tcnt;
for(pii p:g[a[i].id]) elis.push(p);
}
for(int i=id+1;i<=n;i++){
if(!a[i].imp) continue;
pii ea=elis.front(),eb=g[a[i].id].back();
elis.pop(); g[a[i].id].pop_back();
ans[ea.first][ea.second]=ans[eb.first][eb.second]=++tcnt;
for(pii p:g[a[i].id]) elis.push(p);
}
for(int i=id+1;i<=n;i++){
if(a[i].imp) continue;
pii ea=elis.front(),eb=g[a[i].id].back();
elis.pop(); g[a[i].id].pop_back();
ans[ea.first][ea.second]=ans[eb.first][eb.second]=++tcnt;
for(pii p:g[a[i].id]) elis.push(p);
}
printf("%lld\n",mnans);
for(int i=1;i<n;i++)
printf("2 %d 0 %d 1\n",ans[i][0],ans[i][1]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}
```
::::