题解 P4315 【月下“毛景树”】
树上的链问题，显然可以树链剖分
每条边的边权下推到深度更深的节点上，用线段树维护点权
注意LCA的点所维护的边权不属于两点之间的路径，在修改和计算时要排除
要用两种标记，注意两种标记的优先级
区间覆盖标记下传时要把区间加的标记覆盖掉
当然也可以在一种标记打上之前先下传儿子的标记，同样可以保证正确性，但是会变得很慢
#include<cstdio>
using namespace std;
int n,opt,x,y,z,cnt,tot,out,tt,u[100010],v[100010],w[100010],a[100010],id[100010],at[100010],h[100010],dad[100010],top[100010],dep[100010],size[100010],son[100010];
char c;
struct Edge
{
int next,to;
}e[200010];
struct SegT
{
int mx,l,tag;
}t[400010];
int read()
{
out=0,c=getchar();
while(c<48||c>57){c=getchar();}
while(c>=48&&c<=57){out=(out<<3)+(out<<1)+(c&15),c=getchar();}
return out;
}
void Add(int x,int y)
{
e[++cnt].next=h[x],
e[cnt].to=y,
h[x]=cnt;
}
void DFS1(int x)
{
dep[x]=dep[dad[x]]+1,size[x]=1;
for(int i=h[x];i;i=e[i].next)
{
int y=e[i].to;
if(dad[x]^y)
{
dad[y]=x;
DFS1(y);
size[x]+=size[y];
if(size[son[x]]<size[y]){son[x]=y;}
}
}
}
void DFS2(int x)
{
id[x]=++tot,at[tot]=a[x],
top[x]=x==son[dad[x]]?top[dad[x]]:x;
if(!son[x]){return;}
DFS2(son[x]);
for(int i=h[x];i;i=e[i].next)
{
int y=e[i].to;
if(y^dad[x]&&y^son[x]){DFS2(y);}
}
}
void DFS(int x)
{
DFS1(x);
for(int i=1;i<n;++i)
{
if(dep[u[i]]>dep[v[i]]){a[u[i]]=w[i];}
else{a[v[i]]=w[i];}
}
DFS2(x);
}
int max(int a,int b)
{
return a>b?a:b;
}
void Pushup(int k)
{
t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
void Pushdown(int k,int l,int r)
{
if(l==r){return;}
if(t[k].tag==1)
{
t[k<<1].tag=1,t[k<<1|1].tag=1,
t[k<<1].l=t[k].l,t[k<<1|1].l=t[k].l,
t[k<<1].mx=t[k].l,t[k<<1|1].mx=t[k].l,
t[k].tag=0,t[k].l=0;
}
if(t[k].tag==2)
{
int mid=l+r>>1;
Pushdown(k<<1,l,mid);Pushdown(k<<1|1,mid+1,r);
t[k<<1].tag=2,t[k<<1|1].tag=2,
t[k<<1].l=t[k].l,t[k<<1|1].l=t[k].l,
t[k<<1].mx+=t[k].l,t[k<<1|1].mx+=t[k].l,
t[k].tag=0,t[k].l=0;
}
}
void Build(int k,int l,int r)
{
if(l==r)
{
t[k].mx=at[l];
return;
}
int mid=l+r>>1;
Build(k<<1,l,mid);
Build(k<<1|1,mid+1,r);
Pushup(k);
}
void Changes(int k,int l,int r,int ll,int rr,int x)
{
if(r<ll||rr<l){return;}
if(ll<=l&&r<=rr)
{
Pushdown(k,l,r);
t[k].mx=x,t[k].tag=1,t[k].l=x;
return;
}
Pushdown(k,l,r);
int mid=l+r>>1;
Changes(k<<1,l,mid,ll,rr,x);
Changes(k<<1|1,mid+1,r,ll,rr,x);
Pushup(k);
}
void Changep(int k,int l,int r,int ll,int rr,int x)
{
if(r<ll||rr<l){return;}
if(ll<=l&&r<=rr)
{
Pushdown(k,l,r);
t[k].mx+=x,t[k].tag=2,t[k].l=x;
return;
}
Pushdown(k,l,r);
int mid=l+r>>1;
Changep(k<<1,l,mid,ll,rr,x);
Changep(k<<1|1,mid+1,r,ll,rr,x);
Pushup(k);
}
int Query(int k,int l,int r,int ll,int rr)
{
if(r<ll||rr<l){return -19260817;}
if(ll<=l&&r<=rr){return t[k].mx;}
Pushdown(k,l,r);
int mid=l+r>>1;
return max(Query(k<<1,l,mid,ll,rr),Query(k<<1|1,mid+1,r,ll,rr));
}
void ChangesL(int x,int y,int z)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]){x^=y,y^=x,x^=y;}
Changes(1,1,n,id[top[x]],id[x],z);
x=dad[top[x]];
}
if(dep[x]>dep[y]){x^=y,y^=x,x^=y;}
Changes(1,1,n,id[x]+1,id[y],z);
}
void ChangepL(int x,int y,int z)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]){x^=y,y^=x,x^=y;}
Changep(1,1,n,id[top[x]],id[x],z);
x=dad[top[x]];
}
if(dep[x]>dep[y]){x^=y,y^=x,x^=y;}
Changep(1,1,n,id[x]+1,id[y],z);
}
int LCA(int x,int y)
{
int ans=-19260817;
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]){x^=y,y^=x,x^=y;}
ans=max(ans,Query(1,1,n,id[top[x]],id[x])),
x=dad[top[x]];
}
if(dep[x]>dep[y]){x^=y,y^=x,x^=y;}
ans=max(ans,Query(1,1,n,id[x]+1,id[y]));
return ans;
}
int main()
{
n=read();
for(int i=1;i<n;++i)
{
u[i]=read(),v[i]=read(),w[i]=read();
Add(u[i],v[i]);Add(v[i],u[i]);
}
DFS(1);
Build(1,1,n);
while(1)
{
c=getchar();
while(1)
{
if(c==83){return 0;}
if(c==77){opt=4;break;}
if(c==65){opt=3;break;}
if(c==111){opt=2;break;}
if(c==104){opt=1;break;}
c=getchar();
}
if(opt==1)
{
x=read(),y=read();
if(dep[u[x]]>dep[v[x]]){Changes(1,1,n,id[u[x]],id[u[x]],y);}
else{Changes(1,1,n,id[v[x]],id[v[x]],y);}
}
if(opt==2)
{
x=read(),y=read(),z=read();
ChangesL(x,y,z);
}
if(opt==3)
{
x=read(),y=read(),z=read();
ChangepL(x,y,z);
}
if(opt==4)
{
x=read(),y=read();
printf("%d\n",LCA(x,y));
}
}
}