【BZOJ3784】树上路径——(点分治，noip)

【BZOJ3784】树上路径

---

Description
　　给定一个N个结点的树，结点用正整数1…N编号。每条边有一个正整数权值。用d(a,b）表示从结点a到结点b路边上经过边的权值。其中要求a < b.将这n*(n-1)/2个距离从大到小排序，输出前M个距离值。
Input
　　第一行两个正整数N,M
　　下面N-1行，每行三个正整数a,b,c(a,b<=N，C<=10000)。表示结点a到结点b有一条权值为c的边。
Output
　　共M行，如题所述.
Sample Input
5 10
1 2 1
1 3 2
2 4 3
2 5 4
Sample Output
7
7
6
5
4
4
3
3
2
1
Hint
$N&lt;=50000,M&lt;=Min(300000,n*(n-1) /2)$N<=50000,M<=Min(300000,n∗(n−1)/2)

直接考虑点分治。
首先Dfs得到从当前分治中心到所有子树中的点的距离。
然后将这些距离从大到小排序。
最开始想到借用有序表合并的思想，合并当前子树和原有的子树，但是发现菊花图会卡到$O(n^2)$O(n2)（Splay表示不服，并且认为能够做到O(nlogn)[太长不写]）
然后试图排序之后直接合并，并且在子树中消去重复统计的影响。
但是这里有一个问题：
$\quad \quad$ 首先，我们显然不能够把当前层的所有答案都统计出来（这样直接就是$n^2$n2个数），只能够取比当前的堆中最小值更大的值。
$\quad \quad$ 有鉴于此，我们似乎并不能够确定当前层到底应该加入多少数（由于下一层会pop掉一些非法数据），导致一些本来应该成为答案的数从头到尾都没有加入答案(惨啊)
所以就只好考虑就在当前层处理处所有的合法数据了。
对于每一个距离，记录它从属于当前中心的哪一个儿子节点。当且仅当两个节点不属于同一子树时才能够成为合法答案，即这条链没有重复的边且经过分治中心。
如果枚举的两个端点是来自于同一子树，则第二个节点继续后移知道不属于同一子树为止。
这一过程我们可以记录当前节点接下来第一个到达的节点来加速后移的过程，防止同一子树的点在一段连续区间使得复杂度退化成$O(n^2)$O(n2)。
总的时间复杂度大概可能也许$\tiny _{2333}$2333​ 是$O(nlog^2n+nlognlogm)$O(nlog2n+nlognlogm)(???)

---

$Code$Code

//By Hzyuer
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int Maxn=50005;
const int Inf=0x3f3f3f3f;
inline int read() {
	char c; int rec=0;
	while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();
	return rec;
}
int n,m;
priority_queue< int,vector<int>,greater<int> > Ans; //答案统计 
struct node {int a,b,x;};
inline bool operator < (const node &A,const node &B) {return A.x<B.x;}
priority_queue< node > q; // 端点A,B以及距离x 
struct Branch {int next,to,val;} branch[Maxn<<1];
int h[Maxn],cnt=0;
inline void add(int x,int y,int z) {
	branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; branch[cnt].val=z; return ;
}
int Minn,rtsize,root;
int size[Maxn],vis[Maxn],ind;

int nxt[Maxn],ans[Maxn];
struct Number {int dis,bl;} a[Maxn];
inline bool operator < (const Number &A,const Number &B) {return A.dis>B.dis;} 
//将点排序 
inline void Getroot(int v,int pre) {
	int maxx=0; size[v]=1;
	for(int i=h[v];i;i=branch[i].next) {
		int j=branch[i].to;
		if(j==pre||vis[j]) continue;
		Getroot(j,v); size[v]+=size[j];
		maxx=max(maxx,size[j]);
	}
	maxx=max(maxx,rtsize-size[v]);
	if(Minn>maxx) Minn=maxx,root=v;
}
void Dfs(int v,int pre,int dis) {
	a[++ind].dis=dis;
	for(int i=h[v];i;i=branch[i].next) {
		int j=branch[i].to;
		if(j==pre||vis[j]) continue;
		Dfs(j,v,dis+branch[i].val);
	} return ;
}
inline void Sov(int v) {
	a[ind=1]=(Number){0,v}; //分治中心是需要加入的 
	for(int i=h[v];i;i=branch[i].next) {
		int j=branch[i].to;
		if(vis[j]) continue;
		int temp=ind+1;
		Dfs(j,v,branch[i].val);
		for(int t=temp;t<=ind;++t)
			a[t].bl=j;
	}
	if(ind==1) return ;
	sort(a+1,a+1+ind);
	a[ind+1].bl=-1; a[ind+1].dis=-Inf; //哨兵节点 
	for(int i=ind;i;--i) {
		if(a[i].bl==a[i+1].bl)
			nxt[i]=nxt[i+1];
		else nxt[i]=i+1;
	} // 扫描得出后移位置 
	while(!q.empty()) q.pop();
	for(int i=1;i<=ind;++i)
		q.push((node){i,nxt[i],a[i].dis+a[nxt[i]].dis});
	// 有序表的合并
	// 在q这个堆中时刻维护了过当前分治中心的最长链 
	while(q.top().x>Ans.top()) {
		Ans.pop(); Ans.push(q.top().x);
		int x=q.top().a,y=q.top().b;
		q.pop(); ++y;
		if(a[x].bl==a[y].bl)
			y=nxt[y];
		// 跳转 
		q.push((node){x,y,a[x].dis+a[y].dis});
	} return ;
}
void Divide(int v) {
	int temp=rtsize; vis[v]=1; Sov(v);
	for(int i=h[v];i;i=branch[i].next) {
		int j=branch[i].to;
		if(vis[j]) continue;
		Minn=Inf;
		rtsize=size[j];
		if(rtsize>size[v])
			rtsize=temp-size[v];
		Getroot(j,v);
		Divide(root);
	} return ;
}
int main() {
	n=read(); m=read();
	for(int i=1;i<=m;++i) Ans.push(0);
	for(int i=1;i<n;++i) {
		int x=read(),y=read(),z=read();
		add(x,y,z); add(y,x,z);
	}
	Minn=Inf; rtsize=n;
	Getroot(1,0); Divide(root);
	for(int i=1;i<=m;++i) ans[i]=Ans.top(),Ans.pop();
	for(int i=m;i;--i) cout<<ans[i]<<'\n'; 
	// 从大到小输出答案 
	return 0;
}

---

有没有想过为什么前面给出的时间复杂度是对的？
1、重心在树的最长链上
2、点分序的长度是$nlogn$nlogn的。
也就是说，每一层最先加的都是最大值，第一层一开始就把全局答案最大的几个点加入答案了。
所以我们才能够保证世界复杂度。