III.BZOJ3784: 树上的路径

思路1：

淀粉质。用priority_queue维护前\(m\)长的路径的长度。用multiset维护点分治时，之前所有子树的路径长度，然后对于新子树中的每一条路径，在multiset中从大往小枚举另一半路径拼一起并尝试加入优先队列。如果加入失败，那么对于这个点，集合中再往前的数也不会成功，可以直接跳掉。

这种方法非常显然，但会被长度递增的路径序列卡掉。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[50100],cnt,sz[50100],msz[50100],ROOT,SZ;
priority_queue<int,vector<int>,greater<int> >q;
bool vis[50100];
multiset<int>s;
vector<int>v;
struct node{
	int to,next,val;
}edge[100100];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void getroot(int x,int fa){
	sz[x]=1,msz[x]=0;
	for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getroot(edge[i].to,x),sz[x]+=sz[edge[i].to],msz[x]=max(msz[x],sz[edge[i].to]);
	msz[x]=max(msz[x],SZ-sz[x]);
	if(msz[x]<msz[ROOT])ROOT=x;
}
void getdis(int x,int fa,int DIS){
	v.push_back(DIS);
	for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getdis(edge[i].to,x,DIS+edge[i].val);
}
bool ins(int x){
	if(q.size()<m){q.push(x);return true;}
	if(q.top()<x){q.pop(),q.push(x);return true;}
	return false;
}
void getans(int x){
	s.insert(0);
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(vis[edge[i].to])continue;
		getdis(edge[i].to,x,edge[i].val);
		sort(v.begin(),v.end());
		for(int j=v.size()-1;j>=0;j--)for(multiset<int>::reverse_iterator it=s.rbegin();it!=s.rend();it++)if(!ins(v[j]+*it))break;
		for(int j=0;j<v.size();j++)s.insert(v[j]);
		v.clear();
	}
	s.clear();
}
void solve(int x){
	getans(x),vis[x]=true;
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(vis[edge[i].to])continue;
		ROOT=0,SZ=sz[edge[i].to],getroot(edge[i].to,x),solve(ROOT);
	}
}
int main(){
	scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
	for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
	msz[0]=0x3f3f3f3f,SZ=n,getroot(1,0),solve(ROOT);
	while(!q.empty())v.push_back(q.top()),q.pop();
	for(int i=v.size()-1;i>=0;i--)printf("%d\n",v[i]);
	return 0;
}

思路2：

有一种东西叫做“淀粉徐点分序”，即淀粉质过程中所有访问过的节点所组成的序列，即所有分治树的dfs序的拼接。显然，它的长度是\(O(n\log n)\)的（即淀粉质常规复杂度）。那么它有什么用呢？

我们考虑单次分治的分治树。则对于一个节点来说，一条经过分治树根的路径的另一端，必定存在于分治树中除了它所在的那颗子树外其他的位置。因为整棵分治树在淀粉质时是一段连续的序列，而它所在的子树也是一段连续序列（dfs序的性质），所以节点\(x\)的路径另一端所在位置可以这么表示：\((x,l,r)\)，即一端是点分序中的第\(x\)个位置，另一端可以在点分序中区间\([l,r]\)内的任何位置。这就是[NOI2010]超级钢琴的内容。直接用堆+ST表即可在\(O(n\log n)\)时间内完成。详情可见该题题解，不再赘述。因为总序列长度是\(O(n\log n)\)的，因此总复杂度是\(O(n\log^2n)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[50100],cnt,sz[50100],msz[50100],ROOT,SZ,dfn[1001000],mx[1001000][20],tot,LG[1001000];
int MAX(int x,int y){
	return dfn[x]>dfn[y]?x:y;
}
int CALC(int L,int R){
	int k=LG[R-L+1];
	return MAX(mx[L][k],mx[R-(1<<k)+1][k]);
}
struct node{
	int x,l,r,pla,val;
	node(int u=0,int v=0,int w=0){
		x=u,l=v,r=w;
	}
	node calc(){
		pla=CALC(l,r);
		val=dfn[x]+dfn[pla];
		return *this;
	}
	friend bool operator <(const node &x,const node &y){
		return x.val<y.val;
	}
};
struct Edge{
	int to,next,val;
}edge[100100];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
priority_queue<node>q;
vector<pair<int,int> >v;
vector<node>vv;
bool vis[50100];
void getroot(int x,int fa){
	sz[x]=1,msz[x]=0;
	for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getroot(edge[i].to,x),sz[x]+=sz[edge[i].to],msz[x]=max(msz[x],sz[edge[i].to]);
	msz[x]=max(msz[x],SZ-sz[x]);
	if(msz[x]<msz[ROOT])ROOT=x;
}
void getdis(int x,int fa,int DIS){
	dfn[++tot]=DIS;
	for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].to]&&edge[i].to!=fa)getdis(edge[i].to,x,DIS+edge[i].val);
}
void getans(int x){
	int L=++tot;
	dfn[tot]=0;
	v.clear();
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(vis[edge[i].to])continue;
		pair<int,int>p;
		p.first=tot;
		getdis(edge[i].to,x,edge[i].val);
		p.second=tot+1;
		v.push_back(p);
	}
	int R=tot;
	for(int j=0;j<v.size();j++){
		pair<int,int> x=v[j];
		for(int i=x.first+1;i<=x.second-1;i++)vv.push_back(node(i,L,x.first));
	}
}
void solve(int x){
	getans(x),vis[x]=true;
	for(int i=head[x];i!=-1;i=edge[i].next){
		if(vis[edge[i].to])continue;
		ROOT=0,SZ=sz[edge[i].to],getroot(edge[i].to,x),solve(ROOT);
	}
}
int main(){
	scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
	for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
	msz[0]=0x3f3f3f3f,SZ=n,getroot(1,0),solve(ROOT);
//	for(int i=1;i<=tot;i++)printf("%d ",dfn[i]);puts("");
	for(int i=2;i<=tot;i++)LG[i]=LG[i>>1]+1;
	for(int i=1;i<=tot;i++)mx[i][0]=i;
	for(int j=1;j<=LG[tot];j++)for(int i=1;i+(1<<j)-1<=tot;i++)mx[i][j]=MAX(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
	for(int i=0;i<vv.size();i++)q.push(vv[i].calc());
	while(m--){
		node p=q.top();q.pop();
		printf("%d\n",p.val);
		if(p.pla!=p.l)q.push(node(p.x,p.l,p.pla-1).calc());
		if(p.pla!=p.r)q.push(node(p.x,p.pla+1,p.r).calc());
	}
	return 0;
}