[bzoj1984]月下“毛景树”

Description

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬,爬啊爬,毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果。

“毛景树”上有\(N\)个节点和\(N-1\)条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数:

\(Change\;k\;w\)：将第\(k\)条树枝上毛毛果的个数改变为\(w\)个。

\(Cover\;u\;v\;w\)：将节点\(u\)与节点\(v\)之间的树枝上毛毛果的个数都改变为\(w\)个。

\(Add\;u\;v\;w\)：将节点\(u\)与节点\(v\)之间的树枝上毛毛果的个数都增加\(w\)个。

由于毛毛虫很贪，于是他会有如下询问：

\(Max\;u\;v\)：询问节点\(u\)与节点\(v\)之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数\(N\)。

接下来\(N-1\)行，每行三个正整数\(U_i,V_i\)和\(W_i\)，第\(i+1\)行描述第\(i\)条树枝。表示第\(i\)条树枝连接节点\(U_i\)和节点\(V_i\)，树枝上有\(W_i\)个毛毛果。

接下来是操作和询问，以“\(Stop\)”结束。

Output

对于毛毛虫的每个询问操作，输出一个答案。

Sample Input

4 
1 2 8 
1 3 7 
3 4 9 
Max 2 4 
Cover 2 4 5 
Add 1 4 10 
Change 1 16 
Max 2 4 
Stop

Sample Output

9 
16 

HINT

\(1\;\leq\;N\;\leq\;10^5\),操作+询问数目\(\;\leq\;10^5\)。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过\(10^9\)个。

Solution

把边权转化成边的两端点中深度较大的那个点的点权.

树剖+线段树(注意下传\(lazy\)的细节,以及没被覆盖时值不该是\(0\),因为存在全覆盖成\(0\)的情况)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
#define M 300005
using namespace std;
struct linetree{
    int l,r,m,c,a;
}lt[M];
struct graph{
    int nxt,to,w,n;
}e[M];
char c[10];
int g[N],a[N],b[N],w[N],n,u,v,x,cnt;
int f[N],p[N],dep[N],siz[N],son[N],top[N];
inline void addedge(int x,int y,int w,int n){
    e[++cnt].nxt=g[x];g[x]=cnt;
    e[cnt].to=y;e[cnt].w=w;e[cnt].n=n;
}
inline void dfs1(int u){
    int m=0;siz[u]=1;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dep[e[i].to]){
            f[e[i].to]=u;
            a[e[i].to]=e[i].w;
            b[e[i].n]=e[i].to; 
            dep[e[i].to]=dep[u]+1;
            dfs1(e[i].to);
            siz[u]+=siz[e[i].to];
            if(siz[e[i].to]>m){
                m=siz[e[i].to];
                son[u]=e[i].to;
            }
        }
}
inline void dfs2(int u,int tp){
    top[u]=tp;p[u]=++cnt;w[cnt]=a[u];
    if(son[u]) dfs2(son[u],tp);
    for(int i=g[u];i;i=e[i].nxt)
        if(f[u]!=e[i].to&&son[u]!=e[i].to)
            dfs2(e[i].to,e[i].to);
}
inline void build(int u,int l,int r){
    lt[u].l=l;lt[u].r=r;lt[u].c=-1;
    if(lt[u].l>1;
        build(lef,l,mid);build(rig,mid+1,r);
        lt[u].m=max(lt[lef].m,lt[rig].m);
    }
    else lt[u].m=w[lt[u].l];
}
inline void push(int u){
    int lef=u<<1,rig=u<<1|1;
    if(lt[u].c>=0){
        lt[lef].a=lt[rig].a=0;
        lt[lef].c=lt[rig].c=lt[u].c;
        lt[lef].m=lt[rig].m=lt[u].c;
        lt[u].c=-1;
    }
    if(lt[u].a){
        lt[lef].a+=lt[u].a;
        lt[rig].a+=lt[u].a;
        lt[lef].m+=lt[u].a;
        lt[rig].m+=lt[u].a;
        lt[u].a=0;
    }
}
inline void cover(int u,int l,int r,int k){
    if(lt[u].l>=l&<[u].r<=r){
        lt[u].m=lt[u].c=k;lt[u].a=0;
    }
    else if(lt[u].l>1;
        push(u);
        if(l<=mid) cover(lef,l,r,k);
        if(r>mid) cover(rig,l,r,k);
        lt[u].m=max(lt[lef].m,lt[rig].m);
    }
}
inline void add(int u,int l,int r,int k){
    if(lt[u].l>=l&<[u].r<=r){
        lt[u].m+=k;lt[u].a+=k;
    }
    else if(lt[u].l>1;
        push(u);
        if(l<=mid) add(lef,l,r,k);
        if(r>mid) add(rig,l,r,k);
        lt[u].m=max(lt[lef].m,lt[rig].m);
    }
}
inline int ask(int u,int l,int r){
    if(lt[u].l>=l&<[u].r<=r)
        return lt[u].m;
    if(lt[u].l>1;
        push(u);
        if(l<=mid) ret=max(ret,ask(lef,l,r));
        if(r>mid) ret=max(ret,ask(rig,l,r));
        return ret;
    }
}
inline void cov(int x,int y,int k){
    int lt;
    while(top[x]!=top[y]){
        if(dep[top[x]]p[y]){
        lt=x;x=y;y=lt;
    }
    if(p[x]p[y]){
        lt=x;x=y;y=lt;
    }
    if(p[x]p[y]){
        lt=x;x=y;y=lt;
    }
    if(p[x]