洛谷-P4374-Disruption

$\large\color{blue} {Describe}$

蒟蒻回去颓了十天文化课以后回来的第一题。

分析题意可知，这题可以抽象成给链上的每条边赋值，每条边的权值为这个赋的值和原有值的最小值，然后就是板子了，树剖$log^2$，$LCT$ $log$，这里选择用$LCT$，因为要边转点所以常数还是挺大的。

还有就是注意初始化和要判断无解情况，初始化所有权值和标记为$inf$，统计答案时如果一条边的权为$inf$就输出$-1$

$\large{Code}$：

#pragma region revive
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define son(x,y) t[x].child[y]
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
#ifndef _DEBUG
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++)=(c))
#define io_eof() (IOB.in.p>=IOB.in.pend)
struct IOBUF { struct { char buff[1 << 26], *p, *pend; }in; struct { char buff[1 << 26], *p; }out; IOBUF() { in.p = in.buff; out.p = out.buff; in.pend = in.buff + fread(in.buff, 1, 1 << 26, stdin); }~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); } }IOB;
#endif
template<typename IO>
inl void write(IO x) {
	if (x == 0) return (void)putchar('0');
	if (x < 0)putchar('-'), x = -x;
	static char buf[30];
	char* p = buf;
	while (x) {
		*(p++) = x % 10 + '0';
		x /= 10;
	}
	while (p > buf)putchar(*(--p));
}
inl void writestr(const char *s) { while (*s != 0)putchar(*(s++)); }
template<typename IO>inl void writeln(IO x) { write(x), putchar('\n'); }
template<typename IO>inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s) {
	char *begin = s, c = getchar();
	while (c < 33 || c>127) {
		c = getchar();
	}
	while (c >= 33 && c <= 127) {
		*(s++) = c;
		c = getchar();
	}
	*s = 0;
	return s - begin;
}
template<typename IO>
inl IO read() {
	IO x = 0;
	register bool w = 0;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return w ? -x : x;
}
#pragma endregion
struct node {
	int fa, child[2], w, tag;
	bool filp;
}t[1000001];
inl void change(int x, int w) {
	t[x].w = min(t[x].w, w), t[x].tag = min(t[x].tag, w);
}
inl void reverse(int x) {
	swap(ls(x), rs(x)), t[x].filp ^= 1;
}
inl void pushdown(int x) {
	if (t[x].filp) {
		if (ls(x))reverse(ls(x));
		if (rs(x))reverse(rs(x));
		t[x].filp = 0;
	}
	if (t[x].tag != inf) {
		if (ls(x))change(ls(x), t[x].tag);
		if (rs(x))change(rs(x), t[x].tag);
		t[x].tag = inf;
	}
}
inl bool nroot(int x) { return ls(fa(x)) == x || rs(fa(x)) == x; }
inl bool poi(int x) { return rs(fa(x)) == x; }
inl void push(int x) {
	if (nroot(x))push(fa(x));
	pushdown(x);
}
inl void rotate(int x) {
	re f = fa(x), gf = fa(f), fs = poi(x), gfs = poi(f), s = t[x].child[fs ^ 1];
	if (nroot(f))t[gf].child[gfs] = x;
	t[f].child[fs] = s, t[x].child[fs ^ 1] = f;
	if (s)fa(s) = f;
	fa(x) = gf, fa(f) = x;
}
inl void splay(int x) {
	push(x);
	while (nroot(x)) {
		if (nroot(fa(x)))poi(x) == poi(fa(x)) ? rotate(fa(x)) : rotate(x);
		rotate(x);
	}
}
inl void access(int x) { for (re i = 0; x; x = fa(i = x)) splay(x), rs(x) = i; }
inl void makeroot(int x) { access(x), splay(x), reverse(x); }
inl void split(int x, int y) { makeroot(y), access(x), splay(x); }
inl void link(int x, int y) { split(x, y), fa(y) = x; }
struct edge {
	int u, v;
}e[1000001];
signed main() {
	re n = read<int>(), m = read<int>(), x, y, w;
	for (re i = 0; i <= n; i++)t[i].w = t[i + n].w = inf;
	for (re i = 1; i < n; i++)x = read<int>(), y = read<int>(), e[i] = edge{ x,y }, link(x, i + n), link(y, i + n);
	while (m--) {
		x = read<int>(), y = read<int>(), w = read<int>();
		split(x, y), change(x, w);
	}
	for (re i = 1; i < n; i++)split(e[i].u, e[i].v), writeln(t[i + n].w == inf ? -1 : t[i + n].w);
}