毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有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之间树枝上毛毛果个数最多有多少个。

第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。

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

9
16

【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

题目分析

树剖裸题 注意双标记的写法 我的做法:时刻让两个标记不共存
注意覆盖标记初始-1

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int head[100100],to[200100],net[200100],val[200100],v[100100],value[100100];
int fa[100100],deep[100100],size[100100],son[100100],top[100100],number[100100];
int tot,cnt;
struct your
{
    int x,y;
    int maxx;
    int all,add;
}a[400400];
void add(int x,int y,int c)
{
    net[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    val[tot]=c;
}
void dfs(int x,int temp)
{
    fa[x]=temp;
    deep[x]=deep[fa[x]]+1;
    size[x]=1;
    for(int i=head[x];i;i=net[i])
        if(to[i]!=temp) 
        {
            v[to[i]]=val[i];
            dfs(to[i],x);
            if(size[son[x]]<size[to[i]]) son[x]=to[i];
            size[x]+=size[to[i]];
        }
}
void dfs2(int x,int temp)
{
    top[x]=temp;
    number[x]=++cnt;
    value[cnt]=v[x];
    if(son[x]) dfs2(son[x],temp);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x]&&to[i]!=son[x]) 
            dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy)
    {
        a[num].maxx=value[dx];
        a[num].all=-1;
        return ;
    }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
    a[num].all=-1;
}
void add_push(int num)
{
    if(a[num<<1].all!=-1) a[num<<1].all+=a[num].add;
    else a[num<<1].add+=a[num].add;
    if(a[num<<1|1].all!=-1) a[num<<1|1].all+=a[num].add;
    else a[num<<1|1].add+=a[num].add;
    a[num<<1].maxx+=a[num].add,a[num<<1|1].maxx+=a[num].add;
    a[num].add=0;
}
void all_push(int num)
{
    a[num<<1].add=a[num<<1|1].add=0;
    a[num<<1].all=a[num<<1|1].all=a[num].all;
    a[num<<1].maxx=a[num<<1|1].maxx=a[num].all;
    a[num].all=-1;
}
void update(int dx,int dy,int c,int num,int color)
{
    if(a[num].x==dx&&a[num].y==dy)
    {
        if(color==1)
        {
            if(a[num].all!=-1) a[num].all+=c,a[num].maxx+=c;
            else a[num].add+=c,a[num].maxx+=c;
        }
        else a[num].all=c,a[num].maxx=c,a[num].add=0;
        return ;
    }
    if(a[num].add) add_push(num);
    if(a[num].all!=-1) all_push(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) update(dx,dy,c,num<<1|1,color);
    else if(dy<=mid) update(dx,dy,c,num<<1,color);
    else update(dx,mid,c,num<<1,color),update(mid+1,dy,c,num<<1|1,color);
    a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
}
int ask(int dx,int dy,int num)
{
    if(a[num].x==dx&&a[num].y==dy) return a[num].maxx;
    if(a[num].add) add_push(num);
    if(a[num].all!=-1) all_push(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) return ask(dx,dy,num<<1|1);
    if(dy<=mid) return ask(dx,dy,num<<1);
    return max(ask(dx,mid,num<<1),ask(mid+1,dy,num<<1|1));
}
void change(int x,int y,int c,int color)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        update(number[top[x]],number[x],c,1,color);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    if(x!=y) update(number[x]+1,number[y],c,1,color);
}
int find(int x,int y)
{
    int tmp=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        tmp=max(tmp,ask(number[top[x]],number[x],1));
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    if(x!=y) tmp=max(tmp,ask(number[x]+1,number[y],1));
    return tmp;
}
char s[100];
struct my
{
    int x,y;
}way[2000000];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        way[i].x=x,way[i].y=y;
        add(x,y,c),add(y,x,c);
    }
    dfs(1,0),dfs2(1,1);
    build(1,n,1);
    scanf("%s",&s[0]);
    while(s[0]!='S')
    {
        if(s[0]=='M')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",find(x,y));
        }
        else if(s[1]=='o')
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            change(x,y,c,2);
        }
        else if(s[0]=='A')
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            change(x,y,c,1);
        }
        else if(s[1]=='h')
        {
            int x,c;
            scanf("%d%d",&x,&c);
            if(deep[way[x].x]>deep[way[x].y]) swap(way[x].x,way[x].y);
            change(way[x].x,way[x].y,c,2);
        }
        scanf("%s",&s[0]);
    }
    return 0;
}