[Vani has a date] tail on rainy days

  Portal ：luogu4556[Vani There's a date ] The tail of a rainy day

  Today, we are mainly going to learn about the merging of line segments and trees , But it feels so simple Write a dynamic opening point and it's gone qwq.

The main idea of the topic

  Here's a tree for you , also $m$ operations , Select one at a time from $x$ To $y$ The path of , Then put a type of $z$ The items . After the operation is completed, the number of the type with the most items in all nodes is output , If there are the same number, output the one with small number .

analysis

  First of all, when I see this problem , Immediately thought of the difference in the tree . After the difference, we have to consider how to make prefix and .

  If all kinds of objects are the same , Then make prefix and $dfs$ Just do it again . But now it's different , So we have to consider the merging of segment trees .

  The difference part of the tree must not open a bucket at every point , Then the space must blow up , So let's consider the overall situation and open a $vector$ To record the difference , Then when the line segment tree is merged, it is taken out for processing .

  Then the merged part of the line segment tree , It is equivalent to opening a segment tree at each point , The number of the most item types in the subtree used to record this point $dat$ And quantity $num$, It is worth noting that , Segment tree is a maintenance value range （ Types of goods ） The information of .

  The rest is the board that combines the difference on the tree and the segment tree .

#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;
}