51Nod 1558 树中的配对

题目链接

分析：

想了好久~~~还是得看题解...QwQ

首先因为是排列，所以我们猜想要把式子拆开来看， $ \sum dis(i,p[i])=\sum dep[i]+dep[p[i]]-2*dep[lca[i,p[i]]] $ ，定义 $ dep[i] $ 代表 $ i $ 到根节点的距离...

也就是说，其实我们只需要最小化$\sum dep[lca[i],p[i]]$...

我们如果考虑贪心的思想，那么显然$i$和$p[i]$不在一棵子树中的时候$lca$为$root$，那么$dep[lca]$为$0$，所以考虑能否找到一个合法的根节点，使得点两两配对并且不在一个子树中...

显然是可以的，这个优秀的根节点就是重心...

考虑重心的性质，去掉重心之后，每棵子树的大小都不会超多$\frac {n}{2}$，所以说一定存在合法的解...

那么考虑如何解决字典序最小的问题...

如果$u$和$v$匹配，但是$v$不一定和$u$匹配，所以我们把每个点拆成两个点，一个代表下标，一个代表排列，如果我们要找当前点匹配点，那么我们就去找到最大的子树，判断$size$是否刚好为当前点数的一半，如果是，那么我们就必须在这棵子树中找答案，否则就在非$u$的子树中找答案，然后在$u$的子树中删去$u$的下标点，在答案的子树中删去答案的排列点，然后用线段树维护子树内的标号最小值...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<set>

//by NeighThorn

#define inf 0x3f3f3f3f

#define Pa pair<int,int>

using namespace std;

const int maxn=100000+5;

int n,G,cnt,tim,w[maxn<<1],hd[maxn],to[maxn<<1],nxt[maxn<<1];

int be[maxn],en[maxn],siz[maxn],sub[maxn],maxsiz[maxn];

long long ans,dis[maxn];

set< pair<int,int> > s;

set< pair<int,int> >::iterator it;

struct M{

	int l,r,Min;

}tree[maxn<<2];

inline void add(int x,int y,int s){

	w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;

}

inline void dfs(int x,int fa){

	siz[x]=1;

	for(int i=hd[x];i!=-1;i=nxt[i])

		if(to[i]!=fa)

			dfs(to[i],x),siz[x]+=siz[to[i]],maxsiz[x]=max(maxsiz[x],siz[to[i]]);

	maxsiz[x]=max(maxsiz[x],n-siz[x]);

}

inline void findG(void){

	G=1;

	for(int i=2;i<=n;i++)

		if(maxsiz[G]>maxsiz[i]) G=i;

}

inline void dfs(int x,int fa,int top){

	sub[x]=top;siz[x]=1;be[x]=++tim;

	for(int i=hd[x];i!=-1;i=nxt[i])

		if(to[i]!=fa)

			dis[to[i]]=dis[x]+w[i],dfs(to[i],x,top),siz[x]+=siz[to[i]];

	en[x]=tim;

}

inline void build(int l,int r,int tr){

	tree[tr].l=l,tree[tr].r=r,tree[tr].Min=inf;

	if(l==r) return;

	int mid=(l+r)>>1;

	build(l,mid,tr<<1),build(mid+1,r,tr<<1|1);

}

inline void change(int x,int val,int tr){

	if(tree[tr].l==tree[tr].r){

		tree[tr].Min=val;return;

	}

	int mid=(tree[tr].l+tree[tr].r)>>1;

	if(x<=mid)

		change(x,val,tr<<1);

	else

		change(x,val,tr<<1|1);

	tree[tr].Min=min(tree[tr<<1].Min,tree[tr<<1|1].Min);

}

inline int query(int l,int r,int tr){

	if(l>r) return inf;

	if(tree[tr].l==l&&tree[tr].r==r)

		return tree[tr].Min;

	int mid=(tree[tr].l+tree[tr].r)>>1;

	if(r<=mid)

		return query(l,r,tr<<1);

	else if(l>mid)

		return query(l,r,tr<<1|1);

	else

		return min(query(l,mid,tr<<1),query(mid+1,r,tr<<1|1));

}

inline void Minus(int x){

	s.erase(s.find(Pa(siz[x],x)));

	siz[x]--;

	s.insert(Pa(siz[x],x));

}

signed main(void){

#ifndef ONLINE_JUDGE

	freopen("in.txt","r",stdin);

#endif

	scanf("%d",&n);

	memset(hd,-1,sizeof(hd));

	for(int i=1,x,y,l;i<n;i++)

		scanf("%d%d%d",&x,&y,&l),add(x,y,l),add(y,x,l);

	dfs(1,0);findG();memset(siz,0,sizeof(siz));be[G]=++tim;

	for(int i=hd[G];i!=-1;i=nxt[i]) dis[to[i]]=dis[G]+w[i],dfs(to[i],G,to[i]),siz[G]+=siz[to[i]],siz[to[i]]<<=1;siz[G]++;siz[G]<<=1;

	for(int i=hd[G];i!=-1;i=nxt[i]) s.insert(Pa(siz[to[i]],to[i]));s.insert(Pa(siz[G],G));

	build(1,n,1);en[G]=be[G];sub[G]=G;

	for(int i=1;i<=n;i++) ans+=dis[i]<<1;

	cout<<ans<<endl;

	for(int i=1;i<=n;i++) change(be[i],i,1);

	for(int i=1,x;i<=n;i++){

		Minus(sub[i]);

		it=s.lower_bound(Pa(n-i+1,0));

		if(it!=s.end()&&it->first==n-i+1)

			x=query(be[it->second],en[it->second],1);

		else

			x=min(query(1,be[sub[i]]-1,1),query(en[sub[i]]+1,n,1)),x=min(x,query(be[G],be[G],1));

		printf("%d ",x);Minus(sub[x]);change(be[x],inf,1);

	}

	return 0;

}

By NeighThorn

巴特西

51Nod 1558 树中的配对

题目链接

分析：

代码：

最新文章

热门文章