优美的代码

#include <iostream>
#include <vector>
#define int long long 
#define Maxn 100001 
using namespace std;
struct Tree {
    int l,r,val,lazy;
} tr[Maxn*4];
int fa[Maxn],top[Maxn],sz[Maxn],id[Maxn],son[Maxn],dep[Maxn];
int a[Maxn],b[Maxn],n,m;
vector<int>q[Maxn];
void dfs1(int x,int fs)
{
    fa[x]=fs;
    sz[x]=1;
    dep[x]=dep[fs]+1;
    for(int u:q[x]) {
        if(u==fs) continue;
        dfs1(u,x);
        if(sz[u]>sz[son[x]])
            son[x]=u;
        sz[x]+=sz[u];
    }
}
int cnt=0;
void dfs2(int x,int tp) 
{
    top[x]=tp;
    id[x]=++cnt;
    b[cnt]=a[x];
    if(son[x]) dfs2(son[x],tp);
    for(int u:q[x]) {
        if(u==fa[x]||u==son[x])
            continue;
        dfs2(u,u);
    }
}
void build(int x,int l,int r)
{
    if(l == r) {
        tr[x].val=1;
        tr[x].l=tr[x].r=b[l];
        return ;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    tr[x].val=tr[x<<1].val+tr[x<<1|1].val-(tr[x<<1].r==tr[x<<1|1].l&&tr[x<<1].r);
}
void pushdown(int x) {
    if(tr[x].lazy==0)return ;
    tr[x<<1].l=tr[x<<1].r=tr[x<<1|1].l=tr[x<<1|1].r=tr[x].lazy;
    tr[x<<1].val=tr[x<<1|1].val=1;
    tr[x<<1].lazy=tr[x<<1|1].lazy=tr[x].lazy;
    tr[x].lazy=0;
}
void merge(int x,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R)
    {
        tr[x].val=1;
        tr[x].lazy=val;
        tr[x].l=tr[x].r=val;
        return ;
    }
    pushdown(x);
    int mid=l+r>>1;
    if(L<=mid)merge(x<<1,l,mid,L,R,val);
    if(mid<R)merge(x<<1|1,mid+1,r,L,R,val);
    tr[x].val=tr[x<<1].val+tr[x<<1|1].val-(tr[x<<1].r==tr[x<<1|1].l&&tr[x<<1].r);
}
Tree query(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tr[x];
    pushdown(x);
    Tree lson,rson;
    int mid=l+r>>1;
    lson.l=lson.r=lson.val=0;
    rson=lson;
    if(L<=mid)lson=query(x<<1,l,mid,L,R);
    if(mid<R)rson=query(x<<1|1,mid+1,r,L,R);
    tr[x].val=tr[x<<1].val+tr[x<<1|1].val-(tr[x<<1].r==tr[x<<1|1].l&&tr[x<<1].r);
    return {lson.l?lson.l:rson.l,rson.r?rson.r:lson.r,lson.val+rson.val-(lson.r==rson.l&&lson.r),0};
}
int ASK(int u,int v)
{
    Tree x,y;
    x.l=x.r=x.val=0;
    y=x;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<=dep[top[v]])
        {
            Tree res=query(1,1,n,id[top[v]],id[v]);
            y.val=res.val+y.val-(res.r==y.l&&res.r);
            y.l=res.l;
            v=fa[top[v]];
        }
        else {
            Tree res=query(1,1,n,id[top[u]],id[u]);
            x.val=res.val+x.val-(res.r==x.l&&res.r);
            x.l=res.l;
            u=fa[top[u]];
        }
    }
    if(dep[u]<=dep[v])
    {
        Tree res=query(1,1,n,id[u],id[v]);
        y.val=res.val+y.val-(res.r==y.l&&res.r);
        y.l=res.l;
    }
    else {
        Tree res=query(1,1,n,id[top[v]],id[v]);
        x.val=res.val+x.val-(res.r==x.l&&res.r);
        x.l=res.l;
    }
    return x.val+y.val-(x.l==y.l&&x.l);
}
void modify(int u,int v,int val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
            swap(u,v);
        merge(1,1,n,id[top[v]],id[v],val);
        v=fa[top[v]];
    }
    if(dep[u]>dep[v])
        swap(u,v);
    merge(1,1,n,id[u],id[v],val);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        q[u].push_back(v);
        q[v].push_back(u);
    }
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
    while(m--)
    {
        char op;
        int l,r,val;
        cin>>op>>l>>r;
        if(op=='Q')
            cout<<ASK(l,r)<<"\n";
        else {
            cin>>val;
            modify(l,r,val);
        }
    }
    return 0;
}