自动搬运

查看原文

来自洛谷，原作者为

	Miss_SGT **

搬运于2025-08-24 23:14:55，当前版本为作者最后更新于2025-05-06 15:45:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

挺恶心的分讨题。

令 $fa_{x,y}$ 表示以 $1$ 为根时 $x$ 的 $y$ 级祖先，$fa_x$ 表示父亲。

将一对贸易关系 $(A,B,C)$ 的贡献分为：

• $(A,B)$ 都在 $H$ 以 $1$ 为根时的某个儿子的子树内。对 $1$ 到 $\operatorname{lca}$ 的路径上点 $x$，当 $H$ 是 $fa_x$ 并选择了 $x$ 时有贡献。树上差分即可。

• $(A,B)$ 都在 $H$ 以 $1$ 为根时的子树外。对于除了 $1$ 到 $A$ 路径上的点与 $1$ 到 $B$ 路径上的点，有与前一种相同的贡献。求出 $C_i$ 的和，树上差分算补集即可。

• $A$ 在 $H$ 以 $1$ 为根时的某个儿子的子树内，$B$ 在 $H$ 以 $1$ 为根时的子树外（或反过来）。对于 $A$ 到 $fa_{A,(dep_A - dep_{lca} -2)}$ 路径上的点 $x$，有 $H$ 是 $fa_x$ 并同时选择了 $x$ 与 $fa_H$ 时有贡献 ($B$ 同理），树上差分即可。

• $\operatorname{lca}$ 是 $H$。在每个点开个 map，将 $\left(fa_{A,(dep_A - dep_{lca} -1)},fa_{B,(dep_B - dep_{lca} -1)}\right)$ 这个二元组放进 $\operatorname{lca}$ 处的 map 即可简单计算。

值得注意的是：一种选择方案有多种贡献，需要以得当的方式结合；度数小于等于 $1$ 时可以取到所有贡献；在 $(A,B)$ 是祖先关系时需要特殊讨论端点的取舍。

于是我们只需要求 $k$ 级祖先与 $\operatorname{lca}$，加上树上差分变完成了这道题，时间复杂度 $O(n \log n )$。用并查集求祖先与 $\operatorname{lca}$ ，且对于第四种贡献在外层桶排后加入 vector，可以做到 $O(n \alpha(n))$。

int n,m,a[N],b[N],c[N],lca[N],af[N],bf[N],f[N],lst[N];
int find(int x){
	if(f[x]==x) return x;
	int p=f[x];
	f[x]=find(f[x]);
	lst[x]=lst[p]?lst[p]:(lst[x]?lst[x]:x);
	return f[x];
}
vector<int> Q[N];
int stk[N],top,dep[N],fa[N];
void dfs(int p){
	stk[dep[p]=++top]=p;
	f[p]=p;
	for(int i:Q[p])
		if(lca[i]==-1){
			lca[i]=find(a[i]^b[i]^p);
			af[i]=stk[dep[lca[i]]+1];
			bf[i]=lst[a[i]^b[i]^p];
			if(b[i]==p) swap(af[i],bf[i]);
		}else lca[i]=-1;
	for(int o=head[p];o;o=nxt[o])
		if(to[o]^fa[p]) fa[to[o]]=p,dfs(to[o]);
	f[p]=fa[p];--top;
}
#define ll long long
struct node{int u,v,c;};
inline bool cmp(node x,node y){return x.u==y.u?x.v<y.v:x.u<y.u;}
vector<node> T[N];
ll val[N],fv[N],ffv[N],Sum,ans[N];
void solve(int p){
	ll mx=-1;
	for(int o=head[p];o;o=nxt[o]) if(to[o]^fa[p]){
		solve(to[o]);
		val[p]+=val[to[o]],fv[p]+=fv[to[o]],ffv[p]+=ffv[to[o]];
		if(~mx) ans[p]=max(ans[p],mx+val[to[o]]);
		mx=max(mx,val[to[o]]);
	}
	sort(T[p].begin(),T[p].end(),cmp);
	for(int i=0;i<T[p].size();){
		int x=T[p][i].u,y=T[p][i].v;ll res=0;
		while(i<T[p].size()&&T[p][i].u==x&&T[p][i].v==y) res+=T[p][i++].c;
		ans[p]=max(ans[p],res+val[x]+val[y]);
	}
	for(int o=head[p];o;o=nxt[o])if(to[o]^fa[p]){
		ans[p]=max(ans[p],ffv[to[o]]+val[to[o]]+Sum-fv[p]);
	}
	if(!nxt[head[p]]) ans[p]=Sum;
}
int main(){
	read(n),read(m);
	for(int i=1;i<n;++i){
		int u,v;
		read(u),read(v);
		add(u,v),add(v,u);
	}
	for(int i=1;i<=m;++i){
		read(a[i]),read(b[i]),read(c[i]);
		Q[a[i]].push_back(i);
		Q[b[i]].push_back(i);
	}
	dfs(1);
	for(int i=1;i<=m;++i){
		//af bf 表示 A/B 的 dep[A/B] - dep[lca] -1 级祖先 
		if(af[i]&&bf[i]){
			T[lca[i]].push_back((node){min(af[i],bf[i]),max(af[i],bf[i]),c[i]});//第4种 
			val[lca[i]]+=c[i];//第1种 
			fv[fa[a[i]]]+=c[i],fv[fa[b[i]]]+=c[i],fv[lca[i]]-=c[i];//第2种 
		}else{
			val[af[i]^bf[i]]+=c[i];//第1种 
			fv[fa[lca[i]^a[i]^b[i]]]+=c[i];//第2种 
		}
		if(af[i]) ffv[a[i]]+=c[i],ffv[af[i]]-=c[i];
		if(bf[i]) ffv[b[i]]+=c[i],ffv[bf[i]]-=c[i];//第3种 
		Sum+=c[i];
	}
	solve(1);
}