#include "bits/stdc++.h"
using namespace std;
#define MAXN 2000001
struct EDGE{
int Next,To;
}E[MAXN*2];
int Head[MAXN*2],Size;
inline void Add(int From,int To){
E[++Size].Next=Head[From];
Head[From]=Size;
E[Size].To=To;
return;
}
int Fa[MAXN],Tot[MAXN];
int Dep[MAXN],Son[MAXN];
inline void DFS1(int This,int F){
Fa[This]=F;
Tot[This]=1;
int MaxSon=0;
Dep[This]=Dep[F]+1;
for(register int i=Head[This];i;i=E[i].Next){
int To=E[i].To;
if(To==F)continue;
DFS1(To,This);
Tot[This]+=Tot[To];
if(Tot[To]>MaxSon){
MaxSon=Tot[To];
Son[This]=To;
}
}
return;
}
int A[MAXN],InPut[MAXN];
int Count,Top[MAXN],ID[MAXN];
inline void DFS2(int This,int Topf){
Top[This]=Topf;
ID[This]=(++Count);
InPut[Count]=A[This];
if(Son[This]==0)
return;
DFS2(Son[This],Topf);
for(register int i=Head[This];i;i=E[i].Next){
int To=E[i].To;
if(To==Fa[This]||To==Son[This])
continue;
DFS2(To,To);
}
return;
}
struct SegmentTree{
int Left,Right;
int Lazy,Max;
bool Judge;
}Tree[MAXN*4];
inline int LeftSon(int i){return i<<1;}
inline int RightSon(int i){return i<<1|1;}
inline void Build(int i,int Left,int Right){
Tree[i].Left=Left;
Tree[i].Right=Right;
Tree[i].Judge=false;
if(Left==Right){
Tree[i].Max=InPut[Left];
return;
}
int Mid=(Left+Right)>>1;
int L=LeftSon(i),R=RightSon(i);
Build(L,Left,Mid),Build(R,Mid+1,Right);
Tree[i].Max=max(Tree[L].Max,Tree[R].Max);
return;
}
inline void PushDown(int i){
int L=LeftSon(i);
int R=RightSon(i);
if(Tree[i].Judge==true){
Tree[L].Lazy=Tree[i].Lazy;
Tree[R].Lazy=Tree[i].Lazy;
Tree[L].Max=Tree[i].Max;
Tree[R].Max=Tree[i].Max;
Tree[i].Judge=false;
Tree[L].Judge=true;
Tree[R].Judge=true;
return;
}
if(Tree[i].Lazy==0)
return;
Tree[L].Lazy+=Tree[i].Lazy;
Tree[R].Lazy+=Tree[i].Lazy;
Tree[L].Max+=Tree[i].Lazy;
Tree[R].Max+=Tree[i].Lazy;
Tree[i].Lazy=0;
return;
}
inline void Cover(int i,int Left,int Right,int A){
if(Tree[i].Left>Right||Left>Tree[i].Right)
return;
if(Left<=Tree[i].Left&&Tree[i].Right<=Right){
Tree[i].Judge=true;
Tree[i].Lazy=0;
Tree[i].Max=A;
return;
}
PushDown(i);
int L=LeftSon(i),R=RightSon(i);
if(Tree[R].Left<=Right)Cover(R,Left,Right,A);
if(Tree[L].Right>=Left)Cover(L,Left,Right,A);
Tree[i].Max=max(Tree[L].Max,Tree[R].Max);
return;
}
inline void ChaSeg(int i,int V,int A){
if(Tree[i].Right<V||Tree[i].Left>V)
return;
if(Tree[i].Left==Tree[i].Right){
Tree[i].Judge=false;
Tree[i].Max=A;
return;
}
PushDown(i);
int L=LeftSon(i),R=RightSon(i);
if(Tree[L].Right>=V)ChaSeg(L,V,A);
if(Tree[R].Left<=V)ChaSeg(R,V,A);
Tree[i].Max=max(Tree[L].Max,Tree[R].Max);
return;
}
inline void AddSeg(int i,int Left,int Right,int A){
if(Tree[i].Right<Left||Right<Tree[i].Left)
return;
if(Left<=Tree[i].Left&&Tree[i].Right<=Right){
if(Tree[i].Judge==false)
Tree[i].Lazy+=A;
Tree[i].Max+=A;
return;
}
PushDown(i);
int L=LeftSon(i),R=RightSon(i);
if(Tree[L].Right>=Left)AddSeg(L,Left,Right,A);
if(Tree[R].Left<=Right)AddSeg(R,Left,Right,A);
Tree[i].Max=max(Tree[L].Max,Tree[R].Max);
return;
}
inline int MaxSeg(int i,int Left,int Right){
if(Tree[i].Left>Right||Left>Tree[i].Right)
return 0;
if(Left<=Tree[i].Left&&Tree[i].Right<=Right)
return Tree[i].Max;
int Max=0;
PushDown(i);
int L=LeftSon(i),R=RightSon(i);
if(Tree[L].Right>=Left)
Max=max(Max,MaxSeg(L,Left,Right));
if(Tree[R].Left<=Right)
Max=max(Max,MaxSeg(R,Left,Right));
return Max;
}
inline void TreeCover(int X,int Y,int Z){
while(Top[X]!=Top[Y]){
if(Dep[Top[X]]<Dep[Top[Y]])
swap(X,Y);
Cover(1,ID[Top[X]],ID[X],Z);
X=Fa[Top[X]];
}
if(X==Y)return;
if(Dep[X]>Dep[Y])
swap(X,Y);
Cover(1,ID[Son[X]],ID[Y],Z);
return;
}
inline void TreeAdd(int X,int Y,int Z){
while(Top[X]!=Top[Y]){
if(Dep[Top[X]]<Dep[Top[Y]])
swap(X,Y);
AddSeg(1,ID[Top[X]],ID[X],Z);
X=Fa[Top[X]];
}
if(X==Y)return;
if(Dep[X]>Dep[Y])
swap(X,Y);
AddSeg(1,ID[Son[X]],ID[Y],Z);
return;
}
inline int TreeMax(int X,int Y){
int Max=0;
while(Top[X]!=Top[Y]){
if(Dep[Top[X]]<Dep[Top[Y]])
swap(X,Y);
Max=max(Max,MaxSeg(1,ID[Top[X]],ID[X]));
X=Fa[Top[X]];
}
if(X==Y)return Max;
if(Dep[X]>Dep[Y])
swap(X,Y);
Max=max(Max,MaxSeg(1,ID[Son[X]],ID[Y]));
return Max;
}
inline int Read(void){
int X=0,Y=1;char C=getchar();
while(C<'0'||C>'9'){if(C=='-'){Y=-1;}C=getchar();}
while('0'<=C&&C<='9'){X=X*10+(C-'0');C=getchar();}
return (X*Y);
}
string Do;
int X,Y,Dis,Z;
bool Visited[MAXN];
int TurnTo[MAXN],N;
int main(void){
//freopen("BrokenTree.in","r",stdin);
//freopen("BrokenTree.out","w",stdout);
N=Read();
for(register int i=1;i<N;i++){
X=Read(),Y=Read(),Dis=Read();
A[Y]=Dis,TurnTo[i]=Y;
Add(X,Y),Add(Y,X);
}
DFS1(1,0);
DFS2(1,1);
Build(1,1,N);
while(cin>>Do){
if(Do[0]=='S')
break;
X=Read(),Y=Read();
switch(Do[1]){
case 'h':{
A[TurnTo[X]]=Y;
ChaSeg(1,ID[TurnTo[X]],Y);
break;
}
case 'o':{
Z=Read();
TreeCover(X,Y,Z);
break;
}
case 'd':{
Z=Read();
TreeAdd(X,Y,Z);
break;
}
case 'a':{
printf("%d\n",TreeMax(X,Y));
break;
}
}
}
return 0;
}
/*
12
1 2 10
2 3 101
3 5 23
5 11 56
5 12 88
3 10 97
4 6 107
4 7 161
4 8 151
7 9 17
2 4 131
*/
提交记录:
https://www.luogu.com.cn/record/35366542