找出問題了：
正確方式：

    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return tr[rk[r]].dep-tr[rk[l]].dep+1;
            }
    };

完整代碼：

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
    int ft=1,cnt;
    class tree_node
    {
        public:
            int fa,dep,size,hs,top,id;
            vector<int> s;
    };
    int rk[(1<<17)+1];
    tree_node tr[(1<<17)+1];
    void tr_dfs1(int now,int fa,int dep)
    {
        tr[now].fa=fa;
        tr[now].dep=dep;
        tr[now].size=1;
        tr[now].hs=-1;
        for (int i=0;i<tr[now].s.size();i++)
            if (tr[now].s[i]!=fa)
            {
                int next=tr[now].s[i];
                tr_dfs1(next,now,dep+1);
                tr[now].size+=tr[next].size;
                if (tr[now].hs==-1)
                    tr[now].hs=next;
                else if (tr[tr[now].hs].size<tr[next].size)
                    tr[now].hs=next;
            }
    }
    void tr_dfs2(int now,int top)
    {
        tr[now].top=top;
        tr[now].id=++cnt;
        rk[cnt]=now;
        if (tr[now].hs!=-1)
        {
            tr_dfs2(tr[now].hs,top);
            for (int i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                    tr_dfs2(tr[now].s[i],tr[now].s[i]);
        }
    }
    void tr_build()
    {
        cnt=0;
        tr_dfs1(ft,ft,1);
        tr_dfs2(ft,ft);
    }
    int lca(int x,int y)
    {
        while (tr[x].top!=tr[y].top)
        {
            if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                swap(x,y);
            x=tr[tr[x].top].fa;
        }
        if (tr[x].dep<tr[y].dep)
            return x;
        else
            return y;
    }
    
    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return tr[rk[r]].dep-tr[rk[l]].dep+1;
            }
    };
    int data[(1<<17)+1];
    st_node st[(1<<19)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    st_node merge(st_node li,st_node ri)//li:左子區間，ri:右子區間
    {
        if (li.empt)
            return ri;
        else if (ri.empt)
            return li;
        st_node a;
        a.empt=a.iflz=0;
        a.l=li.l,a.r=ri.r,a.mid=li.r;
        a.lans=max(li.lans,li.sum+ri.lans);
        a.rans=max(ri.rans,ri.sum+li.rans);
        a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
        a.sum=li.sum+ri.sum;
        return a;
    }
    void st_pushup(int now)
    {
        st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
    }
    void st_update(int now,int l,int r,int val);
    void st_pushdown(int now)
    {
        if (st[now].iflz)
        {
            st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
            st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
            st[now].iflz=0;
        }
    }
    void st_update(int now,int l,int r,int val)
    {
        if (st[now].l==l&&r==st[now].r)
        {
            st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
            st[now].sum=st[now].len()*val;
            st[now].iflz=1,st[now].numlz=val;
        }
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                st_update(lc(now),l,r,val);
            else if (st[now].mid+1<=l)
                st_update(rc(now),l,r,val);
            else
                st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
            st_pushup(now);
        }
    }
    st_node st_ask(int now,int l,int r)
    {
        if (st[now].l==l&&r==st[now].r)
            return st[now];
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r);
            else
                return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
        }
    }
    void st_build(int now,int l,int r)
    {
        st[now].empt=st[now].iflz=0;
        st[now].l=l,st[now].r=r;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
            st_pushup(now);
        }
        else
        {
            st[now].sum=data[rk[l]];
            st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
        }
    }
    
    void update(int x,int y,int val)
    {
        int i,j,lcan=lca(x,y);
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            st_update(1,tr[tr[i].top].id,tr[i].id,val);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            st_update(1,tr[tr[j].top].id,tr[j].id,val);
        if (tr[i].dep>tr[j].dep)
            swap(i,j);
        st_update(1,tr[i].id,tr[j].id,val);
    }
    st_node cty(st_node stn)
    {
        swap(stn.l,stn.r);
        swap(stn.lans,stn.rans);
        return stn;
    }
    int ask(int x,int y)
    {
        int i,j,lcan=lca(x,y);
        st_node ians,jans,ans;
        ians.iflz=jans.iflz=0;
        ians.empt=jans.empt=1;
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            ians=merge(st_ask(1,tr[tr[i].top].id,tr[i].id),ians);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            jans=merge(st_ask(1,tr[tr[j].top].id,tr[j].id),jans);
        if (tr[i].dep>tr[j].dep)
            swap(i,j),swap(ians,jans);
        jans=merge(st_ask(1,tr[i].id,tr[j].id),jans);
        ans=merge(cty(jans),ians);
        return ans.ans;
    }
    
    int n,m;
    
    void main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&data[i]);
        for (int i=1;i<=n;i++)
            tr[i].s.clear();
        for (int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            tr[x].s.push_back(y);
            tr[y].s.push_back(x);
        }
        if (n>0)
            tr_build();
        st_build(1,1,cnt);
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            int K,x,y;
            scanf("%d%d%d",&K,&x,&y);
            if (K==1)
                printf("%d ",ask(x,y));
            else if (K==2)
            {
                int val;
                scanf("%d",&val);
                update(x,y,val);
            }
        }
        printf("\n");
    }
}

int main()
{
    dts::main();
}

為什麼區間長度不能用深度計算？
這是錯誤的：

    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return tr[r].dep-tr[l].dep+1;
            }
    };

這是正確的：

    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return r-l+1;
            }
    };

剛才AC了
Accepted
/in/foo.cc: In function 'void dts::tr_dfs1(int, int, int)':
/in/foo.cc:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~
/in/foo.cc: In function 'void dts::tr_dfs2(int, int)':
/in/foo.cc:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~

狀態 耗時 記憶體佔用

#1 Accepted 16ms 26.785 MiB
#2 Accepted 15ms 26.789 MiB
#3 Accepted 15ms 26.785 MiB
#4 Accepted 168ms 30.414 MiB
#5 Accepted 163ms 30.312 MiB
#6 Accepted 166ms 30.344 MiB
#7 Accepted 166ms 30.336 MiB
#8 Accepted 356ms 34.043 MiB
#9 Accepted 359ms 33.945 MiB
#10 Accepted 335ms 33.965 MiB

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
    int ft=1,cnt;
    class tree_node
    {
        public:
            int fa,dep,size,hs,top,id;
            vector<int> s;
    };
    int rk[(1<<17)+1];
    tree_node tr[(1<<17)+1];
    void tr_dfs1(int now,int fa,int dep)
    {
        tr[now].fa=fa;
        tr[now].dep=dep;
        tr[now].size=1;
        tr[now].hs=-1;
        for (int i=0;i<tr[now].s.size();i++)
            if (tr[now].s[i]!=fa)
            {
                int next=tr[now].s[i];
                tr_dfs1(next,now,dep+1);
                tr[now].size+=tr[next].size;
                if (tr[now].hs==-1)
                    tr[now].hs=next;
                else if (tr[tr[now].hs].size<tr[next].size)
                    tr[now].hs=next;
            }
    }
    void tr_dfs2(int now,int top)
    {
        tr[now].top=top;
        tr[now].id=++cnt;
        rk[cnt]=now;
        if (tr[now].hs!=-1)
        {
            tr_dfs2(tr[now].hs,top);
            for (int i=0;i<tr[now].s.size();i++)
                if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                    tr_dfs2(tr[now].s[i],tr[now].s[i]);
        }
    }
    void tr_build()
    {
        cnt=0;
        tr_dfs1(ft,ft,1);
        tr_dfs2(ft,ft);
    }
    int lca(int x,int y)
    {
        while (tr[x].top!=tr[y].top)
        {
            if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                swap(x,y);
            x=tr[tr[x].top].fa;
        }
        if (tr[x].dep<tr[y].dep)
            return x;
        else
            return y;
    }
    
    class st_node
    {
        public:
            int l,r,mid,empt=1;
            int lans=0,rans=0,ans=0,sum=0;
            int iflz=0,numlz;
            int len()
            {
                return r-l+1;
            }
    };
    int data[(1<<17)+1];
    st_node st[(1<<19)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    st_node merge(st_node li,st_node ri)//li:左子區間，ri:右子區間
    {
        if (li.empt)
            return ri;
        else if (ri.empt)
            return li;
        st_node a;
        a.empt=a.iflz=0;
        a.l=li.l,a.r=ri.r,a.mid=li.r;
        a.lans=max(li.lans,li.sum+ri.lans);
        a.rans=max(ri.rans,ri.sum+li.rans);
        a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
        a.sum=li.sum+ri.sum;
        return a;
    }
    void st_pushup(int now)
    {
        st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
    }
    void st_update(int now,int l,int r,int val);
    void st_pushdown(int now)
    {
        if (st[now].iflz)
        {
            st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
            st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
            st[now].iflz=0;
        }
    }
    void st_update(int now,int l,int r,int val)
    {
        if (st[now].l==l&&r==st[now].r)
        {
            st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
            st[now].sum=st[now].len()*val;
            st[now].iflz=1,st[now].numlz=val;
        }
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                st_update(lc(now),l,r,val);
            else if (st[now].mid+1<=l)
                st_update(rc(now),l,r,val);
            else
                st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
            st_pushup(now);
        }
    }
    st_node st_ask(int now,int l,int r)
    {
        if (st[now].l==l&&r==st[now].r)
            return st[now];
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r);
            else
                return merge(st_ask(lc(now),l,st[now].mid),st_ask(rc(now),st[now].mid+1,r));
        }
    }
    void st_build(int now,int l,int r)
    {
        st[now].empt=st[now].iflz=0;
        st[now].l=l,st[now].r=r;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
            st_pushup(now);
        }
        else
        {
            st[now].sum=data[rk[l]];
            st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
        }
    }
    
    void update(int x,int y,int val)
    {
        int i,j,lcan=lca(x,y);
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            st_update(1,tr[tr[i].top].id,tr[i].id,val);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            st_update(1,tr[tr[j].top].id,tr[j].id,val);
        if (tr[i].dep>tr[j].dep)
            swap(i,j);
        st_update(1,tr[i].id,tr[j].id,val);
    }
    st_node cty(st_node stn)
    {
        swap(stn.l,stn.r);
        swap(stn.lans,stn.rans);
        return stn;
    }
    int ask(int x,int y)
    {
        int i,j,lcan=lca(x,y);
        st_node ians,jans,ans;
        ians.iflz=jans.iflz=0;
        ians.empt=jans.empt=1;
        for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
            ians=merge(st_ask(1,tr[tr[i].top].id,tr[i].id),ians);
        for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
            jans=merge(st_ask(1,tr[tr[j].top].id,tr[j].id),jans);
        if (tr[i].dep>tr[j].dep)
            swap(i,j),swap(ians,jans);
        jans=merge(st_ask(1,tr[i].id,tr[j].id),jans);
        ans=merge(cty(jans),ians);
        return ans.ans;
    }
    
    int n,m;
    
    void main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&data[i]);
        for (int i=1;i<=n;i++)
            tr[i].s.clear();
        for (int i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            tr[x].s.push_back(y);
            tr[y].s.push_back(x);
        }
        if (n>0)
            tr_build();
        st_build(1,1,cnt);
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            int K,x,y;
            scanf("%d%d%d",&K,&x,&y);
            if (K==1)
                printf("%d ",ask(x,y));
            else if (K==2)
            {
                int val;
                scanf("%d",&val);
                update(x,y,val);
            }
        }
        printf("\n");
    }
}

int main()
{
    dts::main();
}