题目
思路
首先我们解决第一个问题
怎么使值最大？
这个可以通过公式变形来解决
\(ans=\sum_{i=1}^{n}(dep_i+dep_{p_i}-2*dep_{lca_{i,p_i}})=2*\sum_{i=1}^{n}dep_i-2*\sum_{i=1}^{n}dep_{lca_{i,p_i}}\)
下面我们看看这能得到什么
p序列是客观存在的，这是与哪个节点是根节点是没有关系的
所以对于一个固定的根节点，他的最大值也是答案
然而我们已知，对于一个根节点，式子的前半部分的值是固定的，所以我们使后一段尽可能的小，当后一段最小时，这就是答案，并且这个答案就是最大值
为了方便，我们就将根结点定为重心，后半部分很容依旧能得到0
第一部分就解决了
下面来说第二部分
对于编号，我们直接找最小的编号就行了
但是要注意一个情况，
我们将一个点拆成一个入点和出点
就是我们将连接看成单项的
我们定义\(in_u\text{和}out_u\)表示第u个子树还没有匹配的出点，和还没有匹配的入点数量
我们考虑我们是怎样将使最后一段等于0的，也就是选的两个点必须不在同一颗子树
也就是对于任何一颗子树我们必须满足
\(in_u+out_u\le\sum_{i=1}^{i\in 子树}(in_i+out_i)-in_u-out_u\)
也就是说，当某一颗子树\(i\)使这个等式取等号的时候，我们对于当前点，
如果当前点不在这颗最大的子树内，这个点必须与子树\(i\)中的某一个节点匹配
对于\(in\)和\(out\)的维护用线段树维护，
最后我们需要将根特殊考虑，为什么？
因为根可以和任意节点匹配，包括自己
代码
#include<iostream>
#include<vector>
#include<set>
using namespace std;
struct node1
{
int e;
long long w;
};
struct node_set
{
int e;
int w;
friend bool operator < (const node_set &a,const node_set &b)
{
return a.w<b.w;
}
};
struct node_tre
{
int l;
int r;
int maxx;
int s1;//未匹配的入点
int s2;//未匹配的出点
}tre[400005];
int n;
int rt;
int siz[100005];
int bel[100005];
long long dep[100005];
vector<node1> g[100005];
long long ans;
set<int> in[100005];
set<node_set> minn;
void build(int l,int r,int k)
{
tre[k].l=l;
tre[k].r=r;
tre[k].maxx=tre[k].s1=tre[k].s2=0;
if(l==r)
{
tre[k].maxx=in[l].size()*2;
tre[k].s1=in[l].size();
tre[k].s2=in[l].size();
return;
}
int mid=(l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
tre[k].maxx=max(tre[k<<1].maxx,tre[k<<1|1].maxx);
tre[k].s1=tre[k<<1].s1+tre[k<<1|1].s1;
tre[k].s2=tre[k<<1].s2+tre[k<<1|1].s2;
}
void delet1(int u,int k)//减去入点
{
if(tre[k].l>u||tre[k].r<u)
return ;
if(tre[k].l==tre[k].r)
{
tre[k].s1--;
tre[k].maxx=tre[k].s1+tre[k].s2;
return;
}
delet1(u,k<<1);
delet1(u,k<<1|1);
tre[k].maxx=max(tre[k<<1].maxx,tre[k<<1|1].maxx);
tre[k].s1=tre[k<<1].s1+tre[k<<1|1].s1;
tre[k].s2=tre[k<<1].s2+tre[k<<1|1].s2;
}
void delet2(int u,int k)//减去出点
{
if(tre[k].l>u||tre[k].r<u)
return ;
if(tre[k].l==tre[k].r)
{
tre[k].s2--;
tre[k].maxx=tre[k].s1+tre[k].s2;
return;
}
delet2(u,k<<1);
delet2(u,k<<1|1);
tre[k].maxx=max(tre[k<<1].maxx,tre[k<<1|1].maxx);
tre[k].s1=tre[k<<1].s1+tre[k<<1|1].s1;
tre[k].s2=tre[k<<1].s2+tre[k<<1|1].s2;
}
int ask(int k,int fin)
{
if(tre[k].maxx!=fin)
return 0;
if(tre[k].l==tre[k].r)
return tre[k].l;
int t=ask(k<<1,fin);
if(t)
return t;
return ask(k<<1|1,fin);
}
void dfs_fouc(int u,int fa)
{
int maxx=-1;
siz[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].e;
if(v!=fa)
{
dfs_fouc(v,u);
siz[u]+=siz[v];
maxx=max(maxx,siz[v]);
}
}
maxx=max(maxx,n-siz[u]);
if(n/2>=maxx)
rt=u;
}
void dfs_dep(int u,int fa)
{
ans+=dep[u]*2;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].e;
if(v!=fa)
{
dep[v]=dep[u]+g[u][i].w;
dfs_dep(v,u);
}
}
}
void dfs_bel(int u,int fa,int _ind)
{
bel[u]=_ind;
in[_ind].insert(u);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].e;
if(v!=fa)
dfs_bel(v,u,_ind);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
long long w;
cin>>u>>v>>w;
g[u].push_back((node1){v,w});
g[v].push_back((node1){u,w});
}
dfs_fouc(1,0);
dfs_dep(rt,0);
for(int i=0;i<g[rt].size();i++)
dfs_bel(g[rt][i].e,rt,i+1);
bel[rt]=g[rt].size()+1;
in[g[rt].size()+1].insert(rt);
for(int i=1;i<=g[rt].size()+1;i++)
{
set<int>::iterator it=in[i].begin();
minn.insert((node_set){i,*it});
}
cout<<ans<<'\n';
build(1,g[rt].size()+1,1);
for(int i=1;i<=n;i++)
{
int u=ask(1,tre[1].maxx);
if(tre[1].maxx>=n-i+1&&(bel[i]!=u&&u!=g[rt].size()+1))
{
set<int>::iterator it=in[u].begin();
int t=*it;
cout<<t<<' ';
in[u].erase(in[u].find(t));
minn.erase(minn.find((node_set){u,t}));
delet1(u,1);
delet2(bel[i],1);
if(!in[u].empty())
{
it=in[u].begin();
minn.insert((node_set){u,*it});
}
}
else
{
set<node_set>::iterator it1=minn.begin();
node_set t=*it1;
if(t.e==bel[i]&&t.w!=rt)
{
minn.erase(it1);
set<node_set>::iterator it2=minn.begin();
node_set t2=*it2;
minn.insert(t);
t=t2;
}
cout<<t.w<<' ';
delet1(t.e,1);
delet2(bel[i],1);
minn.erase(minn.find(t));
in[t.e].erase(in[t.e].find(t.w));
if(!in[t.e].empty())
{
set<int>::iterator it=in[t.e].begin();
minn.insert((node_set){t.e,*it});
}
}
}
return 0;
}