Solution

比较简单的题目。

假设我们选择了 $H$，和两个连通块 $S$、$T$，那么贡献形如：

1. 两端点都包含在 $S \cup \{H\}$ 中；
2. 两端点都包含在 $T \cup \{H\}$ 中（如果两端点重合会和上一种情况算重，不过不太重要）；
3. 一个端点在 $S$ 中，另一个在 $T$ 中。

我们先不考虑三贡献，使用二维数点 + 贪心可以搞定只有两种贡献时的最大收益。

而我们证明：存在 $3$ 贡献的 $(S,T)$ 对数量为 $O(n+q)$。

考虑建立以 $1$ 为根的有根树。一条路径 $(A,B)$，产生本质影响的 $H$ 必然在 $A \to B$ 的路径上。而除了 LCA 外的所有 $H$，经过的两个邻居（决定 $S$ 和 $T$）必有一个是父节点，所以这样的 $(S,T)$ 只有 $O(n)$ 对；而每个限制只会有一个 LCA，所以 $S$ 和 $T$ 都是儿子的只有 $O(q)$ 对。

所以你暴力做复杂度就是 $O((n+q) \log n)$ 的了，足已通过本题。

唉，我的代码为啥这么丑啊。

(ó﹏ò｡)

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,q,tot,dfn[MAXN],rev[MAXN],sze[MAXN],dep[MAXN],fa[MAXN][20];
vector<int> G[MAXN];
int jumping(int u,int dt) {ffor(i,0,19) if(dt&(1<<i)) u=fa[u][i];return u;}
int lca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	u=jumping(u,dep[u]-dep[v]);
	if(u==v) return u;
	roff(i,19,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];	
}
void dfs(int u,int f) {
	fa[u][0]=f,dep[u]=dep[f]+1;
	ffor(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
	dfn[u]=++tot,sze[u]=1,rev[tot]=u;
	for(auto v:G[u]) if(v!=f) dfs(v,u),sze[u]+=sze[v];
	return ;
}
int pa[MAXN],pb[MAXN],w[MAXN],ad[MAXN];
map<pair<int,int>,int> check[MAXN];
vector<pair<int,int>> upd[MAXN];
map<int,int> out[MAXN];
struct QR {int l,r,u,v,mul;};
vector<QR> qr[MAXN];
int tr[MAXN],ex[MAXN];
void update(int pos,int v) {while(pos<=n) tr[pos]+=v,pos+=pos&-pos;return ;}
int query(int pos) {int ans=0;while(pos) ans+=tr[pos],pos-=pos&-pos;return ans;}
int ans[MAXN];
vector<pair<int,int>> opt[MAXN];
void solve(int u,int f) {
	for(auto v:G[u]) if(v!=f) solve(v,u),ad[u]+=ad[v];
	for(auto pr:opt[u]) {
		int v=pr.first,w=pr.second;
		if(dfn[u]<=dfn[v]&&dfn[v]<=dfn[u]+sze[u]-1) {
			v=jumping(v,dep[v]-dep[u]-1);
			out[u][v]+=w;	
		}
		else out[u][fa[u][0]]+=w;
	}
	vector<int> st;
	for(auto v:G[u]) st.push_back(out[u][v]);
	st.push_back(0),st.push_back(0);
	sort(st.begin(),st.end(),[](int A,int B) {return A>B;});
	ans[u]=st[0]+st[1]+ex[u];
	for(auto pr:check[u]) ans[u]=max(ans[u],ex[u]+out[u][pr.first.first]+out[u][pr.first.second]+pr.second);
	for(auto v:G[u]) if(v!=f) ans[u]=max(ans[u],ex[u]+out[u][v]+out[u][f]+ad[v]);
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,n-1) {
		int u,v;
		cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	}
	dfs(1,0);
	ffor(i,1,q) {
		cin>>pa[i]>>pb[i]>>w[i];
		int lc=lca(pa[i],pb[i]);
		if(pa[i]!=lc&&pb[i]!=lc) {
			int id1=jumping(pa[i],dep[pa[i]]-dep[lc]-1),id2=jumping(pb[i],dep[pb[i]]-dep[lc]-1);
			check[lc][{min(id1,id2),max(id1,id2)}]+=w[i];
			ad[pa[i]]+=w[i],ad[pb[i]]+=w[i],ad[id1]-=w[i],ad[id2]-=w[i];
		}
		else if(pa[i]==pb[i]) ex[pa[i]]+=w[i];
		else if(pa[i]==lc) {
			int id2=jumping(pb[i],dep[pb[i]]-dep[lc]-1);
			ad[pb[i]]+=w[i],ad[id2]-=w[i];	
		}
		else {
			int id1=jumping(pa[i],dep[pa[i]]-dep[lc]-1);
			ad[pa[i]]+=w[i],ad[id1]-=w[i];	
		}
		upd[min(dfn[pa[i]],dfn[pb[i]])].push_back({max(dfn[pa[i]],dfn[pb[i]]),w[i]});
		if(pa[i]!=pb[i]) opt[pa[i]].push_back({pb[i],w[i]}),opt[pb[i]].push_back({pa[i],w[i]});
	}
	ffor(u,1,n) {
		for(auto v:G[u]) {
			if(v!=fa[u][0]) qr[dfn[v]+sze[v]-1].push_back({dfn[v],dfn[v]+sze[v]-1,u,v,1}),qr[dfn[v]-1].push_back({dfn[v],dfn[v]+sze[v]-1,u,v,-1});
			else {
				qr[dfn[u]-1].push_back({1,dfn[u]-1,u,v,1});
				qr[dfn[u]-1].push_back({dfn[u]+sze[u],n,u,v,1});
				qr[dfn[u]+sze[u]-1].push_back({dfn[u]+sze[u],n,u,v,-1});
				qr[n].push_back({dfn[u]+sze[u],n,u,v,1});	
			}
		}
	}
	ffor(i,1,n) {
		for(auto pr:upd[i]) update(pr.first,pr.second);
		for(auto pr:qr[i]) out[pr.u][pr.v]+=(query(pr.r)-query(pr.l-1))*pr.mul;
	}
	solve(1,0);
	ffor(i,1,n) cout<<ans[i]<<' ';
	return 0;
}