[文章目录]
Description
“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： 1.Change k w：将第k条树枝上毛毛果的个数改变为w个。 2.Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。3.Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：4.Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
树链剖分。
光想着注意标记的顺序了。在线段树返回的时候包含关系写反了。。。
另外需要将边上的权值转换到点上，注意的就只是查询修改的时候lca不能被计算。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 151000
using namespace std;
typedef long long ll;
int n;
char st[30];
int head[N],to[N<<1],nxt[N<<1],data[N<<1],id[N<<1],cnt,ate[N],ww[N];
void add(int x,int y,int z,int zz)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
id[cnt]=zz;
}
int fa[N],deep[N],siz[N],son[N],tid[N],top[N],val[N],tot;
void dfs1(int x)
{
deep[x]=deep[fa[x]]+1; siz[x]++;
int tmp=0,y;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
ww[y=to[i]]=data[i];
fa[y]=x; ate[id[i]]=y;
dfs1(y);
siz[x]+=siz[y];
if(siz[y]>tmp) tmp=siz[y],son[x]=y;
}
}
void dfs2(int x,int anc)
{
tid[x]=++tot; val[tot]=ww[x]; top[x]=anc;
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
struct seg
{
int mx[N<<2],lcov[N<<2],ladd[N<<2];
void pushup(int pos) {mx[pos]=max(mx[pos<<1],mx[pos<<1|1]);}
void pushdown(int pos)
{
if(lcov[pos]!=-1)
{
ladd[pos<<1]=ladd[pos<<1|1]=0;
lcov[pos<<1]=lcov[pos<<1|1]=lcov[pos];
mx[pos<<1]=mx[pos<<1|1]=lcov[pos];
lcov[pos]=-1;
}
if(ladd[pos])
{
ladd[pos<<1]+=ladd[pos];
ladd[pos<<1|1]+=ladd[pos];
mx[pos<<1]+=ladd[pos];
mx[pos<<1|1]+=ladd[pos];
ladd[pos]=0;
}
}
void build(int pos,int l,int r)
{
lcov[pos]=-1;
if(l==r) {mx[pos]=val[l]; return ;}
int mid=l+r>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix_change(int pos,int l,int r,int x,int w)
{
if(l==r) {mx[pos]=w; return ;}
int mid=l+r>>1; pushdown(pos);
if(x<=mid) fix_change(pos<<1,l,mid,x,w);
else fix_change(pos<<1|1,mid+1,r,x,w);
pushup(pos);
}
void fix_cover(int pos,int l,int r,int x,int y,int w)
{
if(x<=l&&y>=r) {mx[pos]=w; lcov[pos]=w; ladd[pos]=0; return ;}
int mid=l+r>>1; pushdown(pos);
if(y<=mid) fix_cover(pos<<1,l,mid,x,y,w);
else if(x>mid) fix_cover(pos<<1|1,mid+1,r,x,y,w);
else fix_cover(pos<<1,l,mid,x,y,w),fix_cover(pos<<1|1,mid+1,r,x,y,w);
pushup(pos);
}
void fix_add(int pos,int l,int r,int x,int y,int w)
{
if(x<=l&&y>=r) {mx[pos]+=w; ladd[pos]+=w; return ;}
int mid=l+r>>1; pushdown(pos);
if(y<=mid) fix_add(pos<<1,l,mid,x,y,w);
else if(x>mid) fix_add(pos<<1|1,mid+1,r,x,y,w);
else fix_add(pos<<1,l,mid,x,y,w),fix_add(pos<<1|1,mid+1,r,x,y,w);
pushup(pos);
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return mx[pos];
int mid=l+r>>1,re; pushdown(pos);
if(y<=mid) re=query(pos<<1,l,mid,x,y);
else if(x>mid) re=query(pos<<1|1,mid+1,r,x,y);
else re=max(query(pos<<1,l,mid,x,y),query(pos<<1|1,mid+1,r,x,y));
pushup(pos); return re;
}
}T;
void Change()
{
int x,k; scanf("%d%d",&x,&k);
T.fix_change(1,1,n,tid[ate[x]],k);
}
void Cover()
{
int x,y,w; scanf("%d%d%d",&x,&y,&w);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
T.fix_cover(1,1,n,tid[top[x]],tid[x],w);
x=fa[top[x]];
}
if(x==y) return ;
if(deep[x]>deep[y]) swap(x,y);
T.fix_cover(1,1,n,tid[x]+1,tid[y],w);
}
void Add()
{
int x,y,w; scanf("%d%d%d",&x,&y,&w);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
T.fix_add(1,1,n,tid[top[x]],tid[x],w);
x=fa[top[x]];
}
if(x==y) return ;
if(deep[x]>deep[y]) swap(x,y);
T.fix_add(1,1,n,tid[x]+1,tid[y],w);
}
void Max()
{
int x,y,ans=-1<<30; scanf("%d%d",&x,&y);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,T.query(1,1,n,tid[top[x]],tid[x]));
x=fa[top[x]];
}
if(x==y)
{
printf("%d\n",ans);
return ;
}
if(deep[x]>deep[y]) swap(x,y);
ans=max(ans,T.query(1,1,n,tid[x]+1,tid[y]));
printf("%d\n",ans);
}
int main()
{
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z,i); add(y,x,z,i);
}
dfs1(1);
dfs2(1,1);
T.build(1,1,n);
while(1)
{
scanf("%s",st);
if(st[1]=='t') break;
switch(st[1])
{
case 'h':Change(); break;
case 'o':Cover(); break;
case 'd':Add(); break;
case 'a':Max(); break;
}
}
return 0;
}