Codeforces - Masha and Cactus

题目链接：Codeforces - Masha and Cactus

---

考虑dp[x] 为x的子树中的最大值。

考虑枚举LCA转移，我们可以发现转移是一条链，然后树剖维护链上子节点的和进行优化即可。

考虑转移一条链的时候，我们需要加上这条链上相邻的节点的dp[v]，我们可以对每个点维护一个子节点的sum - 当前节点的dp[x] 然后链上求和就是相邻节点的dp之和。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,f[N],dp[N],dep[N],pos[N],son[N],sz[N],bl[N],cnt,d[N]; 
vector<int> g[N];
struct node{int a,b,c;}; vector<node> v[N];
void dfs1(int x){
	sz[x]=1;
	for(int to:g[x]){
		dep[to]=dep[x]+1;
		dfs1(to); sz[x]+=sz[to];
		if(sz[to]>sz[son[x]]) son[x]=to;
	}
}
void dfs2(int x,int belong){
	pos[x]=++cnt; bl[x]=belong;
	if(son[x]) dfs2(son[x],belong);
	for(int to:g[x]) if(to!=son[x]) dfs2(to,to);
}
inline int lca(int x,int y){
	while(bl[x]!=bl[y]){
		if(dep[bl[x]]<dep[bl[y]]) swap(x,y); x=f[bl[x]];
	}
	return dep[x]>dep[y]?y:x;
}
inline void insert(int x,int v){for(;x<=n;x+=x&(-x)) d[x]+=v;}
inline int ask(int x){int s=0; for(;x;x-=x&(-x)) s+=d[x]; return s;}
inline int ask(int x,int y){
	int res=0;
	while(bl[x]!=bl[y]){
		if(dep[bl[x]]<dep[bl[y]]) swap(x,y);
		res+=ask(pos[x])-ask(pos[bl[x]]-1); x=f[bl[x]];
	}
	if(pos[x]>pos[y]) swap(x,y);
	return res+ask(pos[y])-ask(pos[x]-1);
}
void dfs(int x){
	int tmp=0;
	for(int to:g[x])	dfs(to),tmp+=dp[to];
	dp[x]=tmp;
	for(node i:v[x])	dp[x]=max(dp[x],tmp+ask(i.b,i.a)+i.c);
	insert(pos[x],tmp-dp[x]);
}
signed main(){
	cin>>n>>m;
	for(int i=2;i<=n;i++) scanf("%d",&f[i]),g[f[i]].push_back(i);
	dfs1(1),dfs2(1,1);
	for(int i=1,a,b,c;i<=m;i++) scanf("%d %d %d",&a,&b,&c),v[lca(a,b)].push_back({a,b,c});
	dfs(1); 
	cout<<dp[1];
	return 0;
}