[Vani有约会]雨天的尾巴

  传送门：luogu4556[Vani有约会]雨天的尾巴

  今天主要是来学线段树合并的，但是感觉好简单 写个动态开点就没了qwq。

题目大意

  给你一颗树，还有 $m$ 次操作，每次选取一条从 $x$ 到 $y$ 的路径，然后在这条路径上的所有点上都放上一个类型为 $z$ 的物品。操作完成之后输出所有节点分别的物品最多的类型的编号，如果同样多就输出编号小的。

分析

  首先一看到这个题面，立马想到树上差分。差分完了之后就要考虑怎么做前缀和了。

  如果是所有物品的种类都是同一种，那么做前缀和就 $dfs$ 一遍就行了。但是现在它不一样，所以我们就要考虑线段树合并了。

  树上差分的部分肯定不能每个点都开一个桶，那样空间必定炸掉，所以我们考虑全局开一个 $vector$ 来记录差分，然后在线段树合并的时候再拿出来处理。

  然后线段树合并的部分，相当于每个点开一个线段树，用来记录这个点的子树中最多的物品种类编号 $dat$ 和数量 $num$，值得注意的是，线段树是维护值域（物品种类）信息的。

  剩下的就是树上差分和线段树合并的板子了。

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 100100
#define MAXM MAXN << 2
#define INFI 100100
#define ls(p) t[p].ls
#define rs(p) t[p].rs

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	} 
	return x;
}

int n = 0; int m = 0;
int ans[MAXN] = {
     0 };
vector<int> c[MAXN];
int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int dep[MAXN] = {
     0 };
int f[MAXN][50] = {
     0 };
void prework(int x, int fa){
    
	dep[x] = dep[fa] + 1;
	for(int i = 0; i <= 30; i++) f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x;
		prework(y, x);
	}
}

int Lca(int x, int y){
    
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
    
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

struct Tnode{
    
	int ls, rs;
	int num, dat;
}t[MAXN << 5];
int cnt = 0;
int root[MAXN] = {
     0 };

inline void up(int p){
    
	if(t[ls(p)].num >= t[rs(p)].num) t[p].num = t[ls(p)].num, t[p].dat = t[ls(p)].dat;
	else t[p].num = t[rs(p)].num, t[p].dat = t[rs(p)].dat;
}

void update(int &p, int l, int r, int idx, int val){
    
	if(!p) p = ++cnt;
	if(l == r) {
     t[p].num += val, t[p].dat = l; return; }
	int mid = (l + r) >> 1;
	if(idx <= mid) update(ls(p), l, mid, idx, val);
	else update(rs(p), mid + 1, r, idx, val);
	up(p);
}

int merge(int p, int q, int l, int r){
    
	if(!p or !q) return p + q;
	if(l == r) {
     t[p].num += t[q].num, t[p].dat = l; return p; }
	int mid = (l + r) >> 1;
	t[p].ls = merge(ls(p), ls(q), l, mid);
	t[p].rs = merge(rs(p), rs(q), mid + 1, r);
	up(p); return p;
}

void dfs(int x, int fa){
    
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		dfs(y, x);
		merge(root[x], root[y], 1, INFI);
	}
	for(int i = 0; i < c[x].size(); i++){
    
		int val = c[x][i] > 0 ? 1 : -1;
		int idx = c[x][i] > 0 ? c[x][i] : -c[x][i];
		update(root[x], 1, INFI, idx, val);
	}
	if(t[x].num == 0) ans[x] = 0;
	else ans[x] = t[x].dat;
}

int main(){
    
	n = in; m = in; cnt = n;
	for(int i = 1; i <= n; i++) root[i] = i;
	for(int i = 1; i < n; i++){
    
		int x = in, y = in;
		add(x, y), add(y, x);
	} prework(1, 0);
	for(int i = 1; i <= m; i++){
    
		int x = in, y = in, z = in;
		int lca = Lca(x, y);
		c[x].push_back(z), c[y].push_back(z);
		c[lca].push_back(-z), c[f[lca][0]].push_back(-z);
	} dfs(1, 0);
	for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
	return 0;
}