线段树合并【模板】

>Link

luogu P4556

>Description

有一棵大小为 $n$ 的树一共有 $m$ 次操作每次操作会在 $x$ 到 $y$ 的路径上的所有点放上一个序号为 $z$ 的救济粮求操作完后每个点存放最多的救济粮的编号。

$z\in [1,Z]$

>解题思路

我们可以在每个点建长度为 $Z$ 的权值线段树记录最大值和最大值所在位置。运用树上差分每次操作在 $x$ 和 $y$ 对应的 $z$ 位置上 $+1$在 $lca(x,y)$ 和 $father(lca(x,y))$ 上 $-1$最后下至上将线段树合并。
但是这样会爆空间和时间我们发现实际上运用的空间并没有这么多就可以在每次操作时动态开点进行空间上的优化。每次将线段树合并时假设将 $B$ 合并到 $A$ 上如果其中一个为空就返回另一个那么将左儿子和右儿子分别合并。

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100010
#define NN 8000010
#define Z 100000
using namespace std;

struct edge
{
	int to, nxt;
} e[N * 2];
int n, m, cnt, h[N], lg[N], dep[N], f[N][50], x, y, z;
int ls[NN], rs[NN], mx[NN], id[NN], tot, root[N], ans[N];

int read()
{
	char c = getchar();
	int ret = 0;
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
	{
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret;
}
void write (int x)
{
	if (x < 10) {putchar (x + '0'); return;}
	write (x / 10);
	putchar (x % 10 + '0');
}
void add (int u, int v)
{
	e[++cnt] = (edge){v, h[u]}; h[u] = cnt;
	e[++cnt] = (edge){u, h[v]}; h[v] = cnt;
}
void dfs (int u, int fa)
{
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; i < lg[dep[u]]; i++)
	  f[u][i] = f[f[u][i - 1]][i - 1];
	int v;
	for (int i = h[u]; i; i = e[i].nxt)
	  if ((v = e[i].to) != fa) dfs (v, u);
}
inline int lca (int x, int y)
{
	if (dep[x] < dep[y]) swap(x, y);
	while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1];
	if (x == y) return y;
	for (int i = lg[dep[x]] - 1; i >= 0; i--)
	  if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
inline void pushup (int u)
{
	if (mx[ls[u]] >= mx[rs[u]] || !rs[u])
	  mx[u] = mx[ls[u]], id[u] = id[ls[u]];
	else
	  mx[u] = mx[rs[u]], id[u] = id[rs[u]];
}
inline void add (int &now, int l, int r, int pos, int val)
{
	if (!now) now = ++tot;
	if (l == r)
	{
		mx[now] += val;
		id[now] = l;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) add (ls[now], l, mid, pos, val);
	else add (rs[now], mid + 1, r, pos, val);
	pushup (now);
}
int merge (int a, int b, int l, int r)
{
	if (!a) return b;
	if (!b) return a;
	if (l == r)
	{
		mx[a] += mx[b];
		return a;
	}
	int mid = (l + r) >> 1;
	ls[a] = merge (ls[a], ls[b], l, mid);
	rs[a] = merge (rs[a], rs[b], mid + 1, r);
	pushup (a);
	return a;
	
}
void solve (int u, int fa)
{
	int v;
	for (int i = h[u]; i; i = e[i].nxt)
	  if ((v = e[i].to) != fa)
	  {
	  	solve (v, u);
	  	root[u] = merge (root[u], root[v], 1, Z);
	  }
	if (mx[root[u]]) ans[u] = id[root[u]];
}

int main()
{
//	freopen ("P4556_12.in", "r", stdin);
	n = read(), m = read();
	int u, v;
	for (int i = 1; i < n; i++)
	{
		u = read(), v = read();
		add (u, v);
	}
	for (int i = 1; i <= n; i++)
	  lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	dfs (1, 0);
	for (int i = 1; i <= m; i++)
	{
		x = read(), y = read(), z = read();
//		printf ("1\n");
		int l = lca (x, y);
//		printf ("0\n");
		add (root[x], 1, Z, z, 1);
		add (root[y], 1, Z, z, 1);
		add (root[l], 1, Z, z, -1);
		add (root[f[l][0]], 1, Z, z, -1);
	}
//	printf ("0");
	solve (1, 0);
	for (int i = 1; i <= n; i++)
	  write (ans[i]), putchar (10);
	return 0;
}