题意

给出 \(n\) 个点的树，每个时刻可能出现一条路径 \(A_i\) 或者之前出现的某条路径 \(A_i\) 消失，每条路径有一个权值，求出在每个时刻过后能够找到的权值最大的路径(指所有和该路径有交的路径 \(A\) 的权值和) \(B\) 的权值是多少。

\(n\leq 10^5\)

分析

结论：两条树上路径有交，则一定有一条路径经过另一条路径的 \(lca\).

• 根据上面的性质我们考虑用树形dp的方式求解。

• 将一条路径的权值在每个点 \(x\) 关系分成两种：

  • \(a\) :路径的 \(lca\) 是 \(x\) ；
  • \(b\) :路径的 \(lca\) 是 \(x\) 的祖先；

• 假设现在已经选定了一条路径 \(B\)，那么该路径的权值就是途径所有点的 \(a\) 和 \(lca\) 的 \(b\) 之和 .

• 考虑动态dp,因为树剖之后答案一定可以写成一段轻链+一段重链+一段轻链的形式。

• 然后全局再用一个可删堆维护每条重链的答案即可。

• 总时间复杂度为 \(O(nlog^2n)\)。

注意可删堆取次大值时要两次检查堆顶是否要被删除

代码

#include<bits/stdc++.h>

using namespace std;

#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=1e5 + 7,Nd=N<<2;

int n,m,edc;

int head[N],x[N],y[N],w[N];

struct edge{

	int lst,to;

	edge(){}edge(int lst,int to):lst(lst),to(to){}

}e[N*2];

void Add(int a,int b){

	e[++edc]=edge(head[a],b),head[a]=edc;

	e[++edc]=edge(head[b],a),head[b]=edc;

}

// slpf

int son[N],zson[N],fa[N],dep[N],in[N],top[N],rev[N],down[N],tim;

void dfs1(int u){

	son[u]=1;

	go(u)if(v^fa[u]){

		fa[v]=u,dep[v]=dep[u]+1,dfs1(v);

		son[u]+=son[v];

		if(son[v]>son[zson[u]]) zson[u]=v;

	}

}

void dfs2(int u,int from){

	top[u]=from,in[u]=++tim,rev[tim]=u,down[u]=u;

	if(zson[u]) dfs2(zson[u],from),down[u]=down[zson[u]];

	go(u)if(v^fa[u]&&v^zson[u]) dfs2(v,v);

}

int Lca(int x,int y){

	for(;top[x]^top[y];y=fa[top[y]])

	if(dep[top[x]]>dep[top[y]]) swap(x,y);

	return dep[x]<dep[y]?x:y;

}

//sgt

#define Ls o<<1

#define Rs o<<1|1

struct data{

	LL l,r,s,mx;

	data(){}

	data operator +(const data &rhs)const{

		data res;

		res.l=max(l,s+rhs.l);

		res.r=max(rhs.r,rhs.s+r);

		res.s=s+rhs.s;

		res.mx=max(max(mx,rhs.mx),r+rhs.l);

		return res;

	}

}t[N<<2];

char s[10];

LL addv[Nd],g[Nd],se[Nd];

void st1(int o,LL v){

	t[o].r+=v,t[o].mx+=v;

	addv[o]+=v;

}

void pushup(int o){

	t[o]=t[Ls]+t[Rs];

}

void pushdown(int o){

	if(!addv[o]) return;

	st1(Ls,addv[o]);

	st1(Rs,addv[o]);

	addv[o]=0;

}

void ma(int p,int l,int r,int o,int opt,LL v){

	if(l==r){

		if(!opt){

			t[o].l+=v,t[o].r+=v,t[o].s+=v,t[o].mx+=v;

		}else if(opt==1){

			LL x=v-g[o];g[o]=v;

			t[o].l+=x,t[o].r+=x,t[o].mx+=x;

		}else{

			LL x=v-se[o];se[o]=v;

			t[o].mx+=x;

		}

		return;

	}

	pushdown(o);int mid=l+r>>1;

	if(p<=mid) ma(p,l,mid,Ls,opt,v);

	else ma(p,mid+1,r,Rs,opt,v);

	pushup(o);

}

void mb(int L,int R,int l,int r,int o,LL v){

	if(L>R) return;

	if(L<=l&&r<=R){

		st1(o,v);

		return;

	}

	pushdown(o);int mid=l+r>>1;

	if(L<=mid) mb(L,R,l,mid,Ls,v);

	if(R>mid)  mb(L,R,mid+1,r,Rs,v);

	pushup(o);

}

data query(int L,int R,int l,int r,int o){

	if(L<=l&&r<=R) return t[o];

	pushdown(o);int mid=l+r>>1;

	if(R<=mid) return query(L,R,l,mid,Ls);

	if(L>mid)  return query(L,R,mid+1,r,Rs);

	return query(L,R,l,mid,Ls)+query(L,R,mid+1,r,Rs);

}

struct Heap{

	priority_queue<LL>A,B;

	void push(LL x){A.push(x);}

	void pop(LL x){B.push(x);}

	LL top(){

		while(!B.empty()&&A.top()==B.top()) A.pop(),B.pop();

		return A.empty()?0:A.top();

	}

	LL se(){

		while(!B.empty()&&A.top()==B.top()) A.pop(),B.pop();

		if(A.empty()) return -1;

		LL x=A.top();A.pop();

		while(!B.empty()&&A.top()==B.top()) A.pop(),B.pop();

		if(B.empty()) {A.push(x);return -1;}

		LL y=A.top();A.push(x);

		return y;

	}

}h[N],ans;

LL tans[N];

void upd(int u,int lca,LL v){

	int x=u;

	for(;u;u=fa[top[u]]){

		int gg=fa[top[u]];

		data res=query(in[top[u]],in[down[u]],1,n,1);

		h[gg].pop(res.l);

		if(tans[top[u]]) ans.pop(tans[top[u]]);

		if(u==x&&!lca) ma(in[u],1,n,1,0,v);

		else{

			if(lca) mb(max(in[top[u]],in[lca]+1),in[u],1,n,1,v);

			ma(in[u],1,n,1,1,h[u].top());

		}

		if(h[u].se()!=-1) ma(in[u],1,n,1,2,h[u].se());

		res=query(in[top[u]],in[down[u]],1,n,1);

		h[gg].push(res.l);

		ans.push(tans[top[u]]=res.mx);

	}

}

void pre(int u){

	go(u)if(v^fa[u]) pre(v);

	h[fa[top[u]]].push(0),ans.push(0);

}

int main(){

	n=gi(),m=gi();

	rep(i,1,n-1) Add(gi(),gi());

	dep[1]=1,dfs1(1),dfs2(1,1);

	pre(1);

	rep(i,1,m){

		scanf("%s",s);

		if(s[0]=='+'){

			x[i]=gi(),y[i]=gi(),w[i]=gi();

			int lca=Lca(x[i],y[i]);

			upd(lca,0,w[i]);

			upd(x[i],lca,w[i]);

			upd(y[i],lca,w[i]);

		}else{

			int t=gi(),lca=Lca(x[t],y[t]);

			upd(lca,0,-w[t]);

			upd(x[t],lca,-w[t]);

			upd(y[t],lca,-w[t]);

		}

		printf("%lld\n",ans.top());

	}

	return 0;

}