Tony Zhao

不得不吐槽一下……这题太蛇皮了……（或许是我太久没写线段树相关结果无论是今天比赛还是这道题被线段树虐到死去活来，被水淹没，不知所措……

题目大意

给你一棵边权树，请你维护它，支持：统一更改路径上权值，更改某条边权值，统一增大路径上权值，求路径上最大边权值。

这道题不知道debug了多长时间了……

线段树基本知识：

对于双laz标记可以产生影响的，必须保证只有一个标记，此时下传标记需要对相关信息进行修改，确保可以正常传递相关性质。不要相信“只要限制了就不会重合”的想法。
pushdown()和pushup()的使用。如果确定了祖先端想要确定子孙端就需要进行pushdown，而如果想要从下确定上面而无法直接更改，使用pushup。修改和查询需要pushdown(),建树和修改需要pushup().注意在某个函数中可以既调用pushdown()和pushup()
不要手残= =

还有树剖的知识：

边权转化为点权之后向上各种爬，爬完最后同father之后进行最终跳转的时候记得跳到的是num[tx]+1而且需要条件tx!=ty
pushup()和更新语句的位置关系！！！

大概就是这样。调了好久才调出来啊……GG

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
#define maxN 200010
int n,m,top[maxN],head[maxN<<1],nex[maxN<<1],to[maxN<<1],tot,inx,iny,inz,u[maxN],v[maxN],siz[maxN],cnt,depth[maxN],lazchg[maxN<<2],lazup[maxN<<2];
int num[maxN],fa[maxN],son[maxN],val[maxN<<2],initval[maxN],inittmp[maxN];
char mode[maxN];
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
void dfs1(int pos,int pre)
{
    depth[pos]=depth[pre]+1;
    siz[pos]=1;
    fa[pos]=pre;
    for(int i=head[pos];i;i=nex[i])
        if(to[i]!=pre)
        {
            initval[to[i]]=val[i];
            dfs1(to[i],pos);
            siz[pos]+=siz[to[i]];
            if(siz[son[pos]]<siz[to[i]]) son[pos]=to[i];
        }
    return;
}
void dfs2(int pos,int pre)
{
    num[pos]=++cnt;
    top[pos]=pre;
    inittmp[num[pos]]=initval[pos];
    if(son[pos]) dfs2(son[pos],pre);
    for(int i=head[pos];i;i=nex[i])
        if(to[i]!=fa[pos]&&to[i]!=son[pos])
            dfs2(to[i],to[i]);
    return;
}
void pushup(int pos){val[pos]=max(val[lson],val[rson]);}
void build(int pos,int l,int r)
{
    if(l==r)
    {
        val[pos]=inittmp[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(pos);
    return;
}
void pushdown(int pos)
{
    if(lazup[pos])
    {
        if(lazchg[lson]!=-1) lazchg[lson]+=lazup[pos];
        else lazup[lson]+=lazup[pos];
        if(lazchg[rson]!=-1) lazchg[rson]+=lazup[pos];
        else lazup[rson]+=lazup[pos];
        val[lson]+=lazup[pos];
        val[rson]+=lazup[pos];
        lazup[pos]=0;
    }
    if(lazchg[pos]!=-1)
    {
        lazup[lson]=lazup[rson]=0;
        lazchg[lson]=lazchg[rson]=lazchg[pos];
        val[lson]=val[rson]=lazchg[pos];
        lazchg[pos]=-1;
        lazup[pos]=lazup[lson]=lazup[rson]=0;
    }
}
void change(int pos,int l,int r,int x,int y)
{
    pushdown(pos);
    if(x==l&&x==r)
    {
        val[pos]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(lson,l,mid,x,y);
    else change(rson,mid+1,r,x,y);
    pushup(pos);
}
void addq(int pos,int l,int r,int x,int y,int tg)
{
    pushdown(pos);
    if(x<=l&&r<=y)
    {
        lazup[pos]+=tg;
        val[pos]+=tg;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) addq(lson,l,mid,x,y,tg);
    if(y>mid) addq(rson,mid+1,r,x,y,tg);
    pushup(pos);
}
void add(int tx,int ty,int tz)
{
    while(top[tx]!=top[ty])
    {
        if(depth[top[tx]]<depth[top[ty]]) swap(tx,ty);
        addq(1,1,n,num[top[tx]],num[tx],tz);
        tx=fa[top[tx]];
    }
    if(depth[tx]>depth[ty]) swap(tx,ty);
    if(tx!=ty) addq(1,1,n,num[tx]+1,num[ty],tz);
}
int query(int pos,int l,int r,int x,int y)
{
    pushdown(pos);
    if(x<=l&&r<=y) return val[pos];
    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret=max(ret,query(lson,l,mid,x,y));
    if(y>mid) ret=max(ret,query(rson,mid+1,r,x,y));
    return ret; 
}
int qmax(int tx,int ty)
{
    int ret=0;
    while(top[tx]!=top[ty])
    {
        if(depth[top[tx]]<depth[top[ty]]) swap(tx,ty);
        ret=max(ret,query(1,1,n,num[top[tx]],num[tx]));
        tx=fa[top[tx]];
    }
    if(depth[tx]>depth[ty]) swap(tx,ty);
    if(tx!=ty) ret=max(ret,query(1,1,n,num[tx]+1,num[ty]));
    return ret;
}
void cov(int pos,int l,int r,int x,int y,int z)
{
    pushdown(pos);
    if(x<=l&&r<=y) {val[pos]=z;lazchg[pos]=z;return;}
    int mid=(l+r)>>1;
    if(x<=mid) cov(lson,l,mid,x,y,z);
    if(y>mid) cov(rson,mid+1,r,x,y,z);
    pushup(pos);
}
void cover(int tx,int ty,int tz)
{
    while(top[tx]!=top[ty])
    {
        if(depth[top[tx]]<depth[top[ty]]) swap(tx,ty);
        cov(1,1,n,num[top[tx]],num[tx],tz);
        tx=fa[top[tx]];
    }
    if(depth[tx]>depth[ty]) swap(tx,ty);
    if(tx!=ty) cov(1,1,n,num[tx]+1,num[ty],tz);
}
int main()
{
    scanf("%d",&n);
    memset(lazchg,-1,sizeof lazchg);
    for(int i=1;i<n;++i) scanf("%d%d%d",u+i,v+i,&inx),addedge(u[i],v[i],inx),addedge(v[i],u[i],inx);
    dfs1(1,0);
    cnt=0;
    dfs2(1,1);
    build(1,1,n);
    while(true)
    {
        scanf("%s",mode);
        switch(mode[1])
        {
            case 'h'://Change
            {
                scanf("%d%d",&inx,&iny);
                if(depth[u[inx]]<depth[v[inx]]) swap(u[inx],v[inx]);
                change(1,1,n,num[u[inx]],iny);
                break;
            }
            case 'o'://Cover
            {
                scanf("%d%d%d",&inx,&iny,&inz);
                cover(inx,iny,inz);
                break;
            }
            case 'd'://Add
            {
                scanf("%d%d%d",&inx,&iny,&inz);
                add(inx,iny,inz);
                break;
            }
            case 'a'://Max
            {
                scanf("%d%d",&inx,&iny);
                printf("%d\n",qmax(inx,iny));
                break;
            }
            case 't':return 0;//Stop
        }
    }
}

BZOJ 1984 月下“毛景树”

题目大意