【bzoj3784】树上的路径

3784: 树上的路径

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 789  Solved: 266
[Submit][Status][Discuss]

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<=50000,M<=Min(300000,n*(n-1) /2 )

Source

[Submit][Status][Discuss]



先把树转换成点分治序列，然后做法同NOI2010超级钢琴

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int maxn = 50100;

struct edge{
	int to,w;
};

int s[maxn * 20];

struct data{
	int l,r,pos,ans,w;
	bool operator < (data b) const
	{
		return ans < b.ans;
	}
};

int n,m;
int maxid[20 * maxn][20],length[20 * maxn];
priority_queue<data> Q;
vector<edge> e[maxn];
bool vis[maxn];
int siz[maxn],weight[maxn],id,dfn[maxn],pos[20 * maxn],cmax[20 * maxn],tot;

inline int getint()
{
	int ret = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		ret = ret * 10 + c - '0',c = getchar();
	return ret;
}

inline void dfs_siz(int u,int fa,int t)
{
	siz[u] = weight[u] = 0;
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i].to;
		if (vis[v] || v == fa) continue;
		dfs_siz(v,u,t);
		siz[u] += siz[v];
		weight[u] = max(weight[u],siz[v]);
	}
	siz[u]++;
	weight[u] = max(weight[u],t - siz[u]);
	if (weight[u] < weight[id]) id = u;
}

inline void cal(int u,int fa)
{
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i].to,w = e[u][i].w;
		if (v == u || v == fa) continue;
		dfn[v] = ++tot;
		s[dfn[v]] = s[dfn[u]] + w;
		pos[dfn[v]] = pos[dfn[u]];
		cal(v,u);
	}
}

inline void ST_init()
{
	int cnt = -1;
	for (int i = 1; i <= tot; i++)
	{
		if ((i & -i) == i) cnt++;
		length[i] = cnt;
	}
	for (int i = 1; i <= tot; i++) maxid[i][0] = i;
	for (int j = 1; j <= 20; j++)
		for (int i = 1; i <= tot; i++)
		{
			if (s[maxid[i][j - 1]] > s[maxid[i + (1 << j - 1)][j - 1]])
				maxid[i][j] = maxid[i][j - 1];
			else
				maxid[i][j] = maxid[i + (1 << j - 1)][j - 1];
		}
}

inline int query_maxid(int l,int r) 
{
	int len = length[r - l + 1];
	if (s[maxid[l][len]] > s[maxid[r - (1 << len) + 1][len]]) return maxid[l][len];
	else return maxid[r - (1 << len) + 1][len];
}

inline void solve(int u)
{
	id = 0;
	dfs_siz(u,0,siz[u]);
	u = id;
	dfn[u] = ++tot;
	pos[dfn[u]] = dfn[u];
	s[dfn[u]] = 0;
	int bottom = tot;
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i].to,w = e[u][i].w;
		if (vis[v]) continue;
		dfn[v] = ++tot;
		s[dfn[v]] = s[dfn[u]] + w;
		pos[dfn[v]] = dfn[v];
		cal(v,u);
	}
	cmax[dfn[u]] = dfn[u];
	for (int i = dfn[u] + 1; i <= tot; i++)
	{
		if (s[cmax[i - 1]] > s[i]) cmax[i] = cmax[i - 1];
		else cmax[i] = i;
		Q.push((data){dfn[u],pos[i] - 1,cmax[pos[i] - 1],s[cmax[pos[i] - 1]] + s[i],s[i]});
	}
	vis[u] = 1;
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i].to;
		if (vis[v]) continue;
		solve(v);
	}
}

int main()
{
	n = getint(); m = getint();
	for (int i = 1; i <= n - 1; i++)
	{
		int u = getint(),v = getint(),w = getint();
		e[u].push_back((edge){v,w});
		e[v].push_back((edge){u,w});
	}
	dfs_siz(1,0,0);
	weight[0] = 2147483647;
	solve(1);
	ST_init();
	for (int i = 1; i <= m; i++)
	{
		int l = Q.top().l,r = Q.top().r,pos = Q.top().pos,ans = Q.top().ans,w = Q.top().w;
		Q.pop();
		printf("%d\n",ans);
		int nr = pos - 1,nl = pos + 1;
		if (l <= nr) Q.push((data){l,nr,query_maxid(l,nr),s[query_maxid(l,nr)] + w,w});
		if (nl <= r) Q.push((data){nl,r,query_maxid(nl,r),s[query_maxid(nl,r)] + w,w});
	}
	return 0;
}