题目
 题解
题意：有m条链，每条链链接两个顶点，链存在一个权值w，现在想要挑选一些链，挑选的链中不能出现相同的节点，问可以挑选出的最大的权重是多少

Solution

设 $d p [i]$ 为以第 $i$ 个点位根节点的子树的最优解， $s u m [i]$ 表示表示 $i$ 节点的所有子节点的 $d p$ 和（注意：不包括 $i$ ）
1.第 $i$ 个节点上不出现链，那么 $d p [i] = \sum (d p [k] ∣ k 为 i 的子节点)$ ；
2.第 $i$ 个节点上出现链，如果选择加入这条链，那么 $d p [i] = w (链的权值) + \sum (d p [k] ∣ k 为链上的节点的子节点) = w + \sum (s u m [k] ∣ k 为链上的节点) - \sum (d p [k] ∣ k 为链上的节点)$

Code

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
#define M(a) memset(a,0,sizeof(a))
int l[N],r[N],dp[N],sum[N],c1[N<<1],c2[N<<1],x,y,fa[N][19],tot,h[N],T,n,m,cnt,dep[N],i,lca,z;
struct node{
	int to,ne;
}e[N<<1];
struct kk{
	int u,v,w;
};
vector<kk>p[N];
void addedge(int x,int y){
	e[++tot]=(node){y,h[x]};
	h[x]=tot;
}
int get(int x,int *c){
	int s=0;
	for (;x;x^=x&-x) s+=c[x];
	return s;
}
void add(int x,int y,int *c){
	for (;x<=n*2;x+=x&-x) c[x]+=y;
}
void dfs1(int u,int f){
	l[u]=++cnt;
	fa[u][0]=f;
	for (int i=1;i<19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=f) dep[v]=dep[u]+1,dfs1(v,u);
	r[u]=++cnt;
}
void dfs2(int u,int fa){
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa) dfs2(v,u),sum[u]+=dp[v];
	dp[u]=sum[u];
	for (int i=0;i<p[u].size();i++){
		int x=p[u][i].u,y=p[u][i].v;
		dp[u]=max(dp[u],get(l[x],c1)-get(l[x],c2)+get(l[y],c1)-get(l[y],c2)+p[u][i].w+sum[u]);
	}
	add(l[u],sum[u],c1);add(r[u],-sum[u],c1);
	add(l[u],dp[u],c2);add(r[u],-dp[u],c2);
}
int LCA(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=18;i>=0;i--)
		if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if (x==y) return x;
	for (int i=18;i>=0;i--)
		if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main(){
	scanf("%d",&T);
	for (;T--;){
		scanf("%d%d",&n,&m);
		for (i=1;i<=n;i++) p[i].clear();
		cnt=tot=0;
		M(sum);M(dp);M(c1);M(c2);M(h);
		for (i=1;i<n;i++) scanf("%d%d",&x,&y),addedge(x,y),addedge(y,x);
		dep[0]=-1;
		dfs1(1,0);
		for (i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&z);
			lca=LCA(x,y);
			p[lca].push_back((kk){x,y,z});
		}
		dfs2(1,0);
		printf("%d\n",dp[1]);
	}
}

hdu5293 Tree chain problem

Solution

Code