Warning! : 一个函数如果没有返回值，你也有可能得到正确的结果。因为函数调用完了之后你要返回的东西也许就在内存空间里。但是这么提交你肯定会 WA。别问我怎么知道的。

以下这个函数可以自动将 ans 返回给调用它的 scanf()，然而我们没有写 return ans; 这一句。

int query(int s,int t,int op)
{
    int ans;
    if(op==3)ans=0;
    else if(op==4)ans=-oo;
    else if(op==5)ans=+oo;
    int fs=top[s],ft=top[t];
    while(fs!=ft)
    {
        if(dep[fs]<dep[ft])swap(fs,ft),swap(s,t);
        if(op==2)csq(1,ind[fs],ind[s]);
        else if(op==3)ans+=qsm(1,ind[fs],ind[s]);
        else if(op==4)ans=max(ans,qmx(1,ind[fs],ind[s]));
        else if(op==5)ans=min(ans,qmn(1,ind[fs],ind[s]));
        s=fa[fs];
        fs=top[s];
    }
    if(dep[s]>dep[t])swap(s,t);
    if(op==2)csq(1,ind[son[s]],ind[t]);
    else if(op==3)ans+=qsm(1,ind[son[s]],ind[t]);
    else if(op==4)ans=max(ans,qmx(1,ind[son[s]],ind[t]));
    else if(op==5)ans=min(ans,qmn(1,ind[son[s]],ind[t]));
    ///return ans;   //我们把 return 语句注释
}

下面进入题解

题意：

给定一个 n 个节点 (n<=20000) 的树，每条边都有一个权值。给定 5 种操作，共 m 个 (m<=20000)。

1.C a b ：将 a 边的权值变为 b
2.N a b ：将 a 到 b 路径上的边的权值取相反数
3.MAX a b ：求 a 到 b 的路径上的边的权值最大值
4.MIN a b ：求 a 到 b 的路径上的边的权值最小值
5.SUM a b ：求 a 到 b 的路径上的边的权值和

思路：

做了这么多的树链剖分，不难发现这显然是树链剖分的题。但是为什么我们要做这道题呢？因为它要 300 行。
首先，你得写出一个支持单点修改、区间取反、区间查询最大最小和的线段树。这些函数名打完，再加上树链剖分的基本函数名，就已经 100 行了。
然后等我们打完了所有的函数，一数，248 行。震惊！
具体怎么实现的，请看代码

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 100001
#define ls (node<<1)
#define rs ((node<<1)+1)
#define mid ((l+r)>>1)
#define oo 999999999   //这是两棵枣

using namespace std;

int fst[MX],nxt[MX*2],v[MX*2],w[MX*2],lnum=-1;
int n,m;

void addeg(int nu,int nv,int nw)  //建立枣树
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
    w[lnum]=nw;
}

typedef struct tnode
{
    int l,r;
    int sm,mx,mn;
    int rv;
}treen;

int fa[MX];     //father
int son[MX];    //heavy son
int dep[MX];    //depth
int siz[MX];    //size
int rak[MX];    //rank
int ind[MX];    //index
int top[MX];    //top of heavy chain
int dtf[MX];    //distance to father
int tim;        //count of index

treen tree[MX*8];

void build(int node,int l,int r)//建树
{
    tree[node].l=l;
    tree[node].r=r;
    tree[node].rv=1;
    if(l==r)tree[node].sm=tree[node].mx=tree[node].mn=dtf[rak[l]];
    else
    {
        build(ls,l,mid),build(rs,mid+1,r);
        tree[node].sm=tree[ls].sm+tree[rs].sm;
        tree[node].mx=max(tree[ls].mx,tree[rs].mx);
        tree[node].mn=min(tree[ls].mn,tree[rs].mn);
    }
}

void psd(int node)//下传
{
    int ta,tb;
    if(tree[node].l==tree[node].r)return;
    if(tree[node].rv==-1)
    {
        ta=tree[ls].mn,tb=tree[ls].mx;
        tree[ls].mx=-ta;
        tree[ls].mn=-tb;
        ta=tree[rs].mn,tb=tree[rs].mx;
        tree[rs].mx=-ta;
        tree[rs].mn=-tb;
        tree[ls].sm*=-1;
        tree[rs].sm*=-1;
        tree[ls].rv*=-1;
        tree[rs].rv*=-1;
        tree[node].rv=1;
    }
}

void upd(int node)//上传
{
    if(tree[node].l==tree[node].r)return;
    tree[node].sm=tree[rs].sm+tree[ls].sm;
    tree[node].mx=max(tree[ls].mx,tree[rs].mx);
    tree[node].mn=min(tree[ls].mn,tree[rs].mn);
}

void csm(int node,int p,int x)//单点修改
{
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(l==r)
    {
        tree[node].sm=x;
        tree[node].mn=x;
        tree[node].mx=x;
        return;
    }
    if(p<=mid)csm(ls,p,x);
    else csm(rs,p,x);
    upd(node);
}

void csq(int node,int ql,int qr)//区间取反
{
    int ta,tb;
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)
    {
        ta=tree[node].mx,tb=tree[node].mn;
        tree[node].mx=-tb;
        tree[node].mn=-ta;
        tree[node].sm*=-1;
        tree[node].rv*=-1;
    }
    else if(r<ql||l>qr)return;
    else csq(ls,ql,qr),csq(rs,ql,qr),upd(node);
}

int qsm(int node,int ql,int qr)//区间和
{
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)return tree[node].sm;
    else if(r<ql||l>qr)return 0;
    else return qsm(ls,ql,qr)+qsm(rs,ql,qr);
}

int qmx(int node,int ql,int qr)//区间最大值
{
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)return tree[node].mx;
    else if(r<ql||l>qr)return -oo;
    else return max(qmx(ls,ql,qr),qmx(rs,ql,qr));
}

int qmn(int node,int ql,int qr)//区间最小值
{
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)return tree[node].mn;
    else if(r<ql||l>qr)return +oo;
    else return min(qmn(ls,ql,qr),qmn(rs,ql,qr));
}

void dfs1(int x,int fat,int dp)//其中一棵是枣树
{
    fa[x]=fat;
    dep[x]=dp;
    siz[x]=1;
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]!=fat)
        {
            dtf[v[i]]=w[i],dfs1(v[i],x,dp+1),siz[x]+=siz[v[i]];
            if(son[x]==-1||siz[v[i]]>siz[son[x]])son[x]=v[i];
        }
    }
}

void dfs2(int x,int tp)//另一棵也是枣树
{
    top[x]=tp;
    ind[x]=++tim;
    rak[tim]=x;
    if(son[x]==-1)return;
    dfs2(son[x],tp);
    for(int i=fst[x];i!=-1;i=nxt[i])
        if(v[i]!=fa[x]&&v[i]!=son[x])
            dfs2(v[i],v[i]);
}

void change(int p,int x)//更新某一边的权值
{
    int but;
    if(dep[v[p*2-1]]>dep[v[p*2-2]])but=v[p*2-1];
    else but=v[p*2-2];
    dtf[but]=x;
    csm(1,ind[but],x);
}

int query(int s,int t,int op)//查询合集
{
    int ans;
    if(op==3)ans=0;
    else if(op==4)ans=-oo;
    else if(op==5)ans=+oo;
    int fs=top[s],ft=top[t];
    while(fs!=ft)
    {
        if(dep[fs]<dep[ft])swap(fs,ft),swap(s,t);
        if(op==2)csq(1,ind[fs],ind[s]);
        else if(op==3)ans+=qsm(1,ind[fs],ind[s]);
        else if(op==4)ans=max(ans,qmx(1,ind[fs],ind[s]));
        else if(op==5)ans=min(ans,qmn(1,ind[fs],ind[s]));
        s=fa[fs];
        fs=top[s];
    }
    if(dep[s]>dep[t])swap(s,t);
    if(op==2)csq(1,ind[son[s]],ind[t]);
    else if(op==3)ans+=qsm(1,ind[son[s]],ind[t]);
    else if(op==4)ans=max(ans,qmx(1,ind[son[s]],ind[t]));
    else if(op==5)ans=min(ans,qmn(1,ind[son[s]],ind[t]));
    return ans;
}

void input()//读取是哪一棵枣树
{
    int a,b,c;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        addeg(a,b,c);
        addeg(b,a,c);
    }
    scanf("%d",&m);
}

void work()//呼叫鲁迅
{
    char op[10];
    int a,b;
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,tim);
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='C')change(a,b);
        else if(op[0]=='N')query(a+1,b+1,2);
        else if(op[0]=='S')printf("%d\n",query(a+1,b+1,3));
        else if(op[1]=='A')printf("%d\n",query(a+1,b+1,4));
        else if(op[1]=='I')printf("%d\n",query(a+1,b+1,5));
    }
}

int main()//鲁 OrzOrz
{
    freopen("t.in","r",stdin);
    freopen("1.out","w",stdout);
    for(int i=0;i<MX;i++)son[i]=fst[i]=-1;
    input();
    work();
    return 0;
}