Link-cut Tree，up用维修数列的放法
O(nlogn)

#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)
    {
        tr[now].fa=fa;
        tr[now].dep=tr[tr[now].fa].dep+1;
        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);
                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);
        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();
}

Accepted

状态 耗时 内存占用

#1 Accepted 4ms 256.0KiB
#2 Accepted 3ms 216.0KiB
#3 Accepted 3ms 256.0KiB
#4 Accepted 152ms 4.375MiB
#5 Accepted 139ms 4.219MiB
#6 Accepted 164ms 4.48MiB
#7 Accepted 165ms 4.363MiB
#8 Accepted 298ms 4.75MiB
#9 Accepted 286ms 4.625MiB
#10 Accepted 314ms 4.875MiB
看见大家都是写的树剖。。。我为什么一来就想到了LCT……
在Splay里面维护最大值，左边最大，右边最大，总和等一系列信息。
每次询问先MakeRoot然后再Access，将根节点储存的最大值输出就行了。
（总时间1531ms，估计是这次的评测机比较好。。。）
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
char c;int rec=0,f=1;
while((c=getchar())<'0'||c>'9')if(c=='-')f=-1;
while(c>='0'&&c<='9')rec=rec*10+c-'0',c=getchar();
return rec*f;
}
int n,m;
struct LCT_Tree{
int F,s[2],val,size;
int sum,maxx,pmax[2];
int C,R;
inline void NewNode(int fa,int x){
F=fa;C=R=0;size=1;
val=sum=maxx=pmax[0]=pmax[1]=x;
return ;
}
}tree[100005];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void PMAX(int v,int f){
tree[v].pmax[f]=max(tree[tree[v].s[f]].pmax[f],
tree[tree[v].s[f]].sum+tree[v].val+max(0,tree[tree[v].s[!f]].pmax[f]));
}
inline void Up(int v){
tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size;
tree[v].sum=tree[tree[v].s[0]].sum+tree[v].val+tree[tree[v].s[1]].sum;
tree[v].maxx=max(max(tree[tree[v].s[0]].maxx,tree[tree[v].s[1]].maxx),
max(0,tree[tree[v].s[0]].pmax[1])+tree[v].val+max(0,tree[tree[v].s[1]].pmax[0]));
PMAX(v,0);PMAX(v,1);return ;
}
inline void Same(int v,int x){if(v==0)return ;
tree[v].C=1;tree[v].val=x;tree[v].sum=x*tree[v].size;
tree[v].maxx=tree[v].pmax[0]=tree[v].pmax[1]=max(x,tree[v].sum);
return ;
}
inline void Rev(int v){if(v==0)return ;
tree[v].R^=1;swap(tree[v].s[0],tree[v].s[1]);swap(tree[v].pmax[0],tree[v].pmax[1]);return ;
}
inline void Down(int v){
if(tree[v].C){Same(tree[v].s[0],tree[v].val);Same(tree[v].s[1],tree[v].val);tree[v].C=0;}
if(tree[v].R){Rev(tree[v].s[0]);Rev(tree[v].s[1]);tree[v].R=0;}
return ;
}
inline void Lazy(int v){if(!Isroot(v))Lazy(tree[v].F);Down(v);return ;}
inline void Rot(int v){
int p=tree[v].F,g=tree[p].F;
int t1=v==tree[p].s[1],t2=p==tree[g].s[1];
int ch=tree[v].s[1^t1];
if(!Isroot(p))tree[g].s[t2]=v;tree[ch].F=p;
tree[v].F=g;tree[v].s[1^t1]=p;
tree[p].F=v;tree[p].s[t1]=ch;
Up(p);return;
}
inline void Splay(int v){Lazy(v);
while(!Isroot(v)){
int p=tree[v].F,g=tree[p].F;
if(!Isroot(p))(v==tree[p].s[1])^(p==tree[g].s[0])?Rot(v):Rot(p);
Rot(v);
}Up(v);return;
}
inline void Access(int v){
for(int temp=0;v;temp=v,v=tree[v].F)
{Splay(v);tree[v].s[1]=temp;Up(v);}
return ;
}
inline void Make_Root(int v){Access(v);Splay(v);Rev(v);return ;}
inline void Link(int v1,int v2){Make_Root(v1);tree[v1].F=v2;return ;}
inline int Find_Root(int v){while(!Isroot(v))v=tree[v].F;return v;}
inline void Change(int v1,int v2,int x){Make_Root(v1);Access(v2);Same(Find_Root(v2),x);return ;}
inline void Ask(int v1,int v2){Make_Root(v1);Access(v2);Splay(v2);cout<<tree[v2].maxx<<' ';return ;}
int main(){
n=read();
for(int i=1;i<=n;i++)tree[i].NewNode(0,read());
for(int i=1;i<n;i++)Link(read(),read());
m=read();
int x,y,z;
for(int i=1;i<=m;i++){
int f=read();
if(f==1)Ask(read(),read());
else {
x=read();y=read();z=read();
Change(x,y,z);
}
}cout<<'\n';
return 0;
}

vector竟然如此不受待见QAQ（也有可能是我写废了，卡了好久）。
用vector数组死活只能过3个点，其余TLE；用嵌套vector+resize能过，5000+ms；改成数组以后就2000+ms了。其他题目用vector存图都没有出现过这样的问题...如果有哪位大神知道原因请告知。

思路大概就是树剖+线段树，线段树每个节点维护4个值，分别是区间内最大连续子序列求和、必须从左/右端点开始的最大连续子序列求和、区间求和，利用这些值查询结果什么的，以及Lazy。

2000+ms版本：

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#define MAXN 100010
#define INF 10000000
using namespace std;

int edge[MAXN<<1],pre[MAXN<<1],now[MAXN],tail;

void ADD_EDGE(int u,int v)
{
    edge[++tail]=v;pre[tail]=now[u];now[u]=tail;
    edge[++tail]=u;pre[tail]=now[v];now[v]=tail;
}

int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],nw0[MAXN];

void DFS(int u)
{
    siz[u]=1;
    for(int i=now[u];i;i=pre[i])
    {
        int v=edge[i];
        if(v!=fa[u])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            DFS(v);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}

int tid[MAXN],tidc=0,top[MAXN],nw1[MAXN];

void CONNECT(int u,int tp)
{
    tid[u]=++tidc;
    nw1[tid[u]]=nw0[u];
    top[u]=tp;
    if(son[u]) CONNECT(son[u],tp);
    for(int i=now[u];i;i=pre[i])
    {
        int v=edge[i];
        if(v!=fa[u]&&v!=son[u])
        {
            CONNECT(v,v);
        }
    }
}

#define lson(x) ((x<<1))
#define rson(x) ((x<<1)|1)

struct node
{
    int l,u;
    int vt; 
} N[MAXN<<2];

struct state
{
    int s[4]; //无限制、从左开始、从右开始、全部 
} S[MAXN<<2];

state inline UNION (const state &l,const state &r)
{
    state ans;
    ans.s[0]=l.s[0]>r.s[0]?l.s[0]:r.s[0];
    ans.s[0]=ans.s[0]>(l.s[2]+r.s[1])?ans.s[0]:(l.s[2]+r.s[1]);
    ans.s[1]=l.s[1]>(l.s[3]+r.s[1])?l.s[1]:(l.s[3]+r.s[1]);
    ans.s[2]=r.s[2]>(r.s[3]+l.s[2])?r.s[2]:(r.s[3]+l.s[2]);
    ans.s[3]=l.s[3]+r.s[3];
    return ans;
}

void inline PUSHUP(int i)
{
    S[i]=UNION(S[lson(i)],S[rson(i)]);
}

void inline PUSHDOWN(int i)
{
    if(N[i].vt==INF) return;
    int ls=lson(i),rs=rson(i);
    S[ls].s[3]=(N[ls].u-N[ls].l+1)*N[i].vt;
    S[ls].s[0]=S[ls].s[1]=S[ls].s[2]=max(0,S[ls].s[3]);
    S[rs].s[3]=(N[rs].u-N[rs].l+1)*N[i].vt;
    S[rs].s[0]=S[rs].s[1]=S[rs].s[2]=max(0,S[rs].s[3]);
    N[ls].vt=N[rs].vt=N[i].vt;
    N[i].vt=INF;
}

void BUILD(int l,int u,int i)
{
    N[i].l=l; N[i].u=u; N[i].vt=INF;
    if(l==u)
    {
        S[i].s[3]=nw1[l];
        S[i].s[0]=S[i].s[1]=S[i].s[2]=max(0,nw1[l]);
        return;
    }
    int m=(l+u)>>1;
    BUILD(l,m,lson(i));
    BUILD(m+1,u,rson(i));
    PUSHUP(i);
}

void UPDATE(int l,int u,int val,int i)
{
    if(N[i].l==l&&N[i].u==u)
    {
        N[i].vt=val;
        S[i].s[3]=(u-l+1)*val;
        S[i].s[0]=S[i].s[1]=S[i].s[2]=max(0,S[i].s[3]);
        return;
    }
    PUSHDOWN(i);
    int m=(N[i].l+N[i].u)>>1;
    if(u<=m) UPDATE(l,u,val,lson(i));
    else if(l>m) UPDATE(l,u,val,rson(i));
    else
    {
        UPDATE(l,m,val,lson(i));
        UPDATE(m+1,u,val,rson(i));
    }
    PUSHUP(i);
}

state QUERY(int l,int u,int i)
{
    if(N[i].l==l&&N[i].u==u)
    {
        return S[i];
    }
    PUSHDOWN(i);
    int m=(N[i].l+N[i].u)>>1;
    if(u<=m) return QUERY(l,u,lson(i));
    else if(l>m) return QUERY(l,u,rson(i));
    else return UNION(QUERY(l,m,lson(i)),QUERY(m+1,u,rson(i)));
}

int inline CHECK(int u,int v)
{
    int tpu=top[u],tpv=top[v];
    state su,sv;
    memset(su.s,0,sizeof(su.s));
    memset(sv.s,0,sizeof(sv.s));
    while(tpu!=tpv)
    {
        if(dep[tpu]<dep[tpv])
        {
            swap(u,v);
            swap(tpu,tpv);
            swap(su,sv);
        }
        su=UNION(QUERY(tid[tpu],tid[u],1),su);
        u=fa[tpu];
        tpu=top[u];
    }
    if(dep[u]<dep[v])
    {
        swap(u,v);
        swap(su,sv);
    }
    su=UNION(QUERY(tid[v],tid[u],1),su);
    swap(su.s[1],su.s[2]); //关键！最后是su、sv左侧相接 
    su=UNION(su,sv);
    return su.s[0];
}

void inline CHANGE(int u,int v,int val)
{
    int tpu=top[u],tpv=top[v];
    while(tpu!=tpv)
    {
        if(dep[tpu]<dep[tpv])
        {
            swap(u,v);
            swap(tpu,tpv);
        }
        UPDATE(tid[tpu],tid[u],val,1);
        u=fa[tpu];
        tpu=top[u];
    }
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    UPDATE(tid[u],tid[v],val,1);
}


int main()
{
    int N,M,R;
    int k,a,b,c;
    
    scanf("%d",&N);
    R=N/2;
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&nw0[i]);
    }
    for(int i=1;i<N;i++)
    {
        scanf("%d%d",&a,&b);
        ADD_EDGE(a,b);
    }
    
    siz[0]=0;
    fa[R]=R; dep[R]=0; nw0[R]=nw1[R]=0;
    memset(son,0,sizeof(son));
    DFS(R);
    
    CONNECT(R,R);
    
    BUILD(1,tidc,1);
    
    scanf("%d",&M);
    while(M--)
    {
        scanf("%d%d%d",&k,&a,&b);
        if(k==1)printf("%d ",CHECK(a,b));
        else
        {
            scanf("%d",&c);
            CHANGE(a,b,c);
        }
    }
    printf("\n");
    
    return 0;
}

此题工作量巨大，倒不是因为树链剖分难写，而是因为栈溢出难调。前者花了一个小时；后者调了六个小时，总共用小号交了20遍才过。尝试过手动调大栈空间，结果被编译器忽略；精简递归的变量数，最终也是徒劳；差点要手写栈、改递归为循环了。

再此忠告后三个点 RE 或 TLE (不知道为什么有时RE也会报成TLE) 的同道中人，只需要把树根定义成
numVertex / 2 即可有效减少递归层数，以防爆栈。

说句题外话。由上述做法可推知，后三个点的数据接近链状，而且估计从树根到叶节点的编号是递增的，所以取个中位数作树根，就把树高减半了。出题人还算比较良心，没把点的序号打乱，否则真的只能rand一个根节点了:)

树链剖分+线段树维护
没学过的先学一下树链剖分
每次用线段树查询出到top里的最优子序列以及一些奇怪的东西(这个区间从左往右的最大值 从右往左的最大值和总和)
记得标记不能用0 ，中间可能会修改到0

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010,INF=2099999999;
struct node {
int lmax,rmax,max,sum,lazy,l,r;
node(){lmax=rmax=max=sum=0;lazy=-INF;l=r=0;}
}T[4*N];
int edge[2*N],pre[2*N],now[N],tail,fa[N],depth[N],size[N],son[N],loc[N],nodeid[N],cnt,v[N],top[N],n,m,num;

void add(int u,int v){
edge[++tail]=v;pre[tail]=now[u];now[u]=tail;
edge[++tail]=u;pre[tail]=now[v];now[v]=tail;
}

void dfs(int a){
size[a]=1;
for(int i=now[a];i;i=pre[i]){
int to=edge[i];
if(to!=fa[a]){
depth[to]=depth[a]+1;fa[to]=a;
dfs(to);
size[a]+=size[to];
if(size[to]>size[son[a]]) son[a]=to;
}
}
}

void dfs2(int a,int t){
loc[a]=++cnt;nodeid[cnt]=a;top[a]=t;
if(son[a]) dfs2(son[a],t);
for(int i=now[a];i;i=pre[i]) if(edge[i]!=fa[a] && edge[i]!= son[a]) dfs2(edge[i],edge[i]);
}

node merge(node a,node b){//a为左 b为右 返回合并后的区间
node t;
t.lmax=max(a.lmax,a.sum+b.lmax);
t.rmax=max(b.rmax,b.sum+a.rmax);
t.sum=a.sum+b.sum;
t.max=max(a.max,b.max);
t.max=max(t.max,a.rmax+b.lmax);
return t;
}

void up(int x){
T[x].lmax=max(T[x<<1].lmax,T[x<<1].sum+T[x<<1|1].lmax);
T[x].rmax=max(T[x<<1|1].rmax,T[x<<1|1].sum+T[x<<1].rmax);
T[x].sum=T[x<<1].sum+T[x<<1|1].sum;
T[x].max=max(T[x<<1].max,T[x<<1|1].max);
T[x].max=max(T[x].max,T[x<<1].rmax+T[x<<1|1].lmax);
}
void down(int x){
if(T[x].lazy==-INF) return;
T[x<<1].lazy=T[x<<1|1].lazy=T[x].lazy;//这句话忘记打然后调试了一天TAT
T[x<<1].sum=(T[x<<1].r-T[x<<1].l+1)*T[x].lazy;
T[x<<1|1].sum=(T[x<<1|1].r-T[x<<1|1].l+1)*T[x].lazy;
if(T[x].lazy>=0){
T[x<<1].lmax=T[x<<1].max=T[x<<1].rmax=T[x<<1].sum;
T[x<<1|1].lmax=T[x<<1|1].max=T[x<<1|1].rmax=T[x<<1|1].sum;
}else{
T[x<<1].lmax=T[x<<1].max=T[x<<1].rmax=0;
T[x<<1|1].lmax=T[x<<1|1].max=T[x<<1|1].rmax=0;
}
T[x].lazy=-INF;
}
void build(int x,int l,int r){
T[x].l=l;T[x].r=r;
if(l==r) {
T[x].lmax=T[x].rmax=T[x].max=v[nodeid[l]]>=0? v[nodeid[l]]:0;
T[x].sum=v[nodeid[l]];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
up(x);
}
void change(int x,int l,int r,int L,int R,int d){
if(l<=L && R<=r){
T[x].sum=(T[x].r-T[x].l+1)*d;T[x].lazy=d;
T[x].max=T[x].lmax=T[x].rmax=d>=0?T[x].sum:0;
return;
}
int mid=(L+R)>>1;
down(x);
if(l>mid) change(x<<1|1,l,r,mid+1,R,d);
else if(r<=mid) change(x<<1,l,r,L,mid,d);
else change(x<<1,l,mid,L,mid,d),change(x<<1|1,mid+1,r,mid+1,R,d);
up(x);
}

node ask(int x,int l,int r,int L,int R){
if(l<=L && R<=r) return T[x];
int mid=(L+R)>>1;
down(x);
if(l>mid) return ask(x<<1|1,l,r,mid+1,R);
else if(r<=mid) return ask(x<<1,l,r,L,mid);
else return merge(ask(x<<1,l,mid,L,mid),ask(x<<1|1,mid+1,r,mid+1,R));
}

int query(int u,int v){
node disu,disv;//disu表示lca到上的信息，disv表示v到lca上的信息
for(;top[u]!=top[v];u=fa[top[u]]){
if(depth[top[u]]<depth[top[v]]) swap(u,v),swap(disu,disv);
disu=merge(ask(1,loc[top[u]],loc[u],1,n),disu);
}
if(depth[u]<depth[v]) swap(u,v),swap(disu,disv);
disu=merge(ask(1,loc[v],loc[u],1,n),disu);
swap(disu.lmax,disu.rmax);
disu=merge(disu,disv);
return disu.max;
}

void modify(int u,int v,int c){
for(;top[u]!=top[v];u=fa[top[u]]){
if(depth[top[u]]<depth[top[v]]) swap(u,v);
change(1,loc[top[u]],loc[u],1,n,c);
}
if(depth[u]<depth[v]) swap(u,v);
change(1,loc[v],loc[u],1,n,c);
}

int main(){
//freopen("1620.in","r",stdin);freopen("1620.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
dfs(1);dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int op,a,b,c;
scanf("%d%d%d",&op,&a,&b);
if(op==1)printf("%d ",query(a,b));
else scanf("%d",&c),modify(a,b,c);
}
printf("\n");
return 0;
}

当心爆栈的问题。。。

如果你是pascal的选手，如果你想找AC程序对拍，参考甚至copy，那么就不要再往下找了，本人程序精简可读性强哦

type
point = record
t,l,r,lm,rm,max,sum,same,lch,rch : longint;
tag : boolean;
end;
arrayType = record
x,y : longint;
end;
var
st_cnt : longint;
st : array[1..300000] of point;

path_cnt : longint;
top,path_s : array[1..100000] of longint;

s,h,rank,belong,f,base,pos : array[0..100001] of longint;
hash : array[1..100000] of boolean;

e : array[1..200001] of arrayType;
n,m,i,k,x,y,c : longint;

function max(x,y:longint):longint;
begin
max := x; if y > x then exit(y);
end;

function max(x,y,z:longint):longint;
begin
max := max(max(x,y),z);
end;

procedure sort(l,r:longint);
var
i,j : longint;
x,y : arrayType;
begin
i:=l;
j:=r;
x:=e[(l+r) div 2];
repeat
while (e[i].x<x.x) do inc(i);
while (x.x<e[j].x) do dec(j);
if not(i>j) then
begin
y:=e[i]; e[i]:=e[j]; e[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

function merge(i:longint;x,y:point):point;
begin
merge.t := i;
merge.tag := false; merge.lch := x.t; merge.rch := y.t;
merge.l := x.l; merge.r := y.r;
merge.sum := x.sum + y.sum;
merge.lm := max(x.lm,x.sum+y.lm);
merge.rm := max(y.rm,y.sum+x.rm);
merge.max := max(x.max,y.max,x.rm+y.lm);
end;

procedure pushtag(i,c:longint);
begin
st[i].tag := true; st[i].same := c; st[i].sum := (st[i].r-st[i].l+1)*c;
if c < 0 then
begin
st[i].lm := c; st[i].rm := c; st[i].max := c; exit;
end;
st[i].lm := st[i].sum; st[i].rm := st[i].sum; st[i].max := st[i].sum;
end;

procedure downtag(i:longint);
begin
if st[i].tag then
begin
st[i].tag := false;
pushtag(st[i].lch,st[i].same);
pushtag(st[i].rch,st[i].same);
end;
end;

procedure build(i,l,r:longint);
var
mid : longint;
begin
st[i].t := i; st[i].l := l; st[i].r := r; st[i].tag := false;
if l = r then exit;
mid := (l+r) shr 1;
inc(st_cnt); st[i].lch := st_cnt; build(st[i].lch,l,mid);
inc(st_cnt); st[i].rch := st_cnt; build(st[i].rch,mid+1,r);
end;

function ask(i,l,r:longint):point;
var
mid : longint;
x,y : point;
begin
if (l <= st[i].l) and (st[i].r <= r) then exit(st[i]);
mid := (st[i].l+st[i].r) shr 1;
downtag(i);
if l > mid then exit(ask(st[i].rch,l,r));
if r <= mid then exit(ask(st[i].lch,l,r));
x := ask(st[i].lch,l,r);
y := ask(st[i].rch,l,r);
ask := merge(1,x,y);
end;

procedure change(i,l,r,c:longint);
var
mid,lch,rch : longint;
begin
if (l <= st[i].l) and (st[i].r <= r) then
begin
pushtag(i,c);
exit;
end;
mid := (st[i].l+st[i].r) shr 1;
downtag(i);
if l <= mid then change(st[i].lch,l,r,c);
if r > mid then change(st[i].rch,l,r,c);
st[i] := merge(i,st[st[i].lch],st[st[i].rch]);
end;

procedure query(a,b:longint);
var
lx,ly,lmid,ans : point;
x,y,temp : longint;
begin
x := belong[a]; y:= belong[b];
lx.lm := 0; lx.rm := 0; lx.max := 0; lx.sum := 0;
ly.lm := 0; ly.rm := 0; ly.max := 0; ly.sum := 0;
while x <> y do
begin
if h[top[x]] > h[top[y]] then
begin
lx := merge(1,lx,ask(x,rank[a],path_s[x]));
a := f[top[x]];
x := belong[a];
end else begin
ly := merge(1,ly,ask(y,rank[b],path_s[y]));
b := f[top[y]];
y := belong[b];
end;
end;
if rank[a] < rank[b] then
begin
lmid := ask(x,rank[a],rank[b]);
lx := merge(1,lx,lmid);
temp := ly.lm; ly.lm := ly.rm; ly.rm := temp;
ans := merge(1,lx,ly);
end else begin
lmid := ask(x,rank[b],rank[a]);
ly := merge(1,ly,lmid);
temp := lx.lm; lx.lm := lx.rm; lx.rm := temp;
ans := merge(1,ly,lx);
end;
write(ans.max,' ');
end;

procedure same(a,b,c:longint);
var
x,y,temp : longint;
begin
x := belong[a]; y:= belong[b];
while x <> y do
begin
if h[top[x]] > h[top[y]] then
begin
change(x,rank[a],path_s[x],c);
a := f[top[x]];
x := belong[a];
end else begin
change(y,rank[b],path_s[y],c);
b := f[top[y]];
y := belong[b];
end;
end;
if h[a] < h[b] then begin temp := a; a := b; b := temp; end;
change(x,rank[a],rank[b],c);
end;

procedure init(t,hi:longint);
var
i,maxch : longint;
begin
hash[t] := true; h[t] := hi; maxch := 0; s[t] := 1;
for i := pos[t] to pos[t+1]-1 do
begin
if hash[e[i].y] then continue;
f[e[i].y] := t;
init(e[i].y,hi+1);
inc(s[t],s[e[i].y]);
if s[e[i].y] > s[maxch] then maxch := e[i].y;
end;
if maxch = 0 then
begin
inc(path_cnt);
path_s[path_cnt] := 1;
top[path_cnt] := t;
rank[t] := 1;
belong[t] := path_cnt; exit;
end;
belong[t] := belong[maxch];
top[belong[t]] := t;
inc(path_s[belong[t]]);
rank[t] := rank[maxch] + 1;
end;

begin
readln(n);
for i := 1 to n do read(base[i]);
for i := 1 to n-1 do
begin
readln(e[i].x,e[i].y);
e[i+n-1].x := e[i].y; e[i+n-1].y := e[i].x;
end;
sort(1,(n-1) shl 1);
for i := (n-1) shl 1 downto 1 do pos[e[i].x] := i; pos[n+1] := n shl 1-1;

init(1,1);
st_cnt := path_cnt;
for i := 1 to path_cnt do build(i,1,path_s[i]);
for i := 1 to n do same(i,i,base[i]);

readln(m);
for i := 1 to m do
begin
read(k,x,y);
case k of
1 : query(x,y);
2 : begin readln(c); same(x,y,c); end;
end;
end;
writeln;
end.

AC了好欢乐

当我前面什么都没说，树链剖分+SGT200+行水过1Y：
编译成功

foo.cpp: In constructor 'state::state(int, int, int, int)':
foo.cpp:51:26: warning: 'state::maxl' will be initialized after [-Wreorder]
foo.cpp:51:19: warning: 'int state::maxr' [-Wreorder]
foo.cpp:55:2: warning: when initialized here [-Wreorder]
测试数据 #0: Accepted, time = 29 ms, mem = 36964 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 36964 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 36960 KiB, score = 10
测试数据 #3: Accepted, time = 399 ms, mem = 40868 KiB, score = 10
测试数据 #4: Accepted, time = 296 ms, mem = 40872 KiB, score = 10
测试数据 #5: Accepted, time = 307 ms, mem = 40868 KiB, score = 10
测试数据 #6: Accepted, time = 296 ms, mem = 40872 KiB, score = 10
测试数据 #7: Accepted, time = 610 ms, mem = 44772 KiB, score = 10
测试数据 #8: Accepted, time = 577 ms, mem = 44772 KiB, score = 10
测试数据 #9: Accepted, time = 779 ms, mem = 44768 KiB, score = 10
Accepted, time = 3355 ms, mem = 44772 KiB, score = 100

//*****************************************************分割线***********************************************************

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define AddEdge( s , t ) Add( s , t ) , Add( t , s )
#define MAXN 100010
#define left( t ) ( t << 1 )
#define right( t ) ( left( t ) ^ 1 )

struct edge {
edge *next ;
int t ;
} *head[ MAXN ] ;

void Add( int s , int t ) {
edge *p = new( edge ) ;
p -> t = t , p -> next = head[ s ] ;
head[ s ] = p ;
}

int arr[ MAXN ] , first[ MAXN ] , child[ MAXN ] , size[ MAXN ] , h[ MAXN ] , cnt = 0 , num[ MAXN ] ;
bool f[ MAXN ] ;
int value[ MAXN ] , n , up[ MAXN ][ 21 ] , m ;

void dfs0( int v ) {
f[ v ] = false , size[ v ] = 1 , child[ v ] = 0 ;
int ret = 0 ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
h[ p -> t ] = h[ v ] + 1 , up[ p -> t ][ 0 ] = v ;
dfs0( p -> t ) ;
if ( size[ p -> t ] > ret ) {
ret = size[ p -> t ] , child[ v ] = p -> t ;
}
size[ v ] += size[ p -> t ] ;
}
}

void dfs1( int v , int u ) {
first[ v ] = u , f[ v ] = false , arr[ num[ v ] = ++ cnt ] = v ;
if ( child[ v ] ) {
dfs1( child[ v ] , u ) ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
dfs1( p -> t , p -> t ) ;
}
}
}

struct state {
int sum , maxs , maxr , maxl ;
state( ) {
sum = maxs = maxl = maxr = 0 ;
}
state( int _sum , int _maxs , int _maxl , int _maxr ) : sum( _sum ) , maxs( _maxs ) , maxl( _maxl ) , maxr( _maxr ) {

}
};

state operator + ( const state &x , const state &y ) {
state ret ;
ret.sum = x.sum + y.sum ;
ret.maxl = max( x.maxl , x.sum + y.maxl ) ;
ret.maxr = max( y.maxr , y.sum + x.maxr ) ;
ret.maxs = max( max( x.maxs , y.maxs ) , x.maxr + y.maxl ) ;
return ret ;
}

struct node {
int l , r , sum , maxs , maxl , maxr , v ;
bool flag ;
node( ) {
sum = maxs = maxl = maxr = 0 ;
flag = false ;
}
} sgt[ MAXN << 3 ] ;

void pushdown( int t ) {
if ( sgt[ t ].flag ) {
sgt[ t ].sum = sgt[ t ].v * ( sgt[ t ].r - sgt[ t ].l + 1 ) ;
sgt[ t ].maxs = sgt[ t ].maxl = sgt[ t ].maxr = sgt[ t ].v > 0 ? sgt[ t ].sum : sgt[ t ].v ;
sgt[ t ].flag = false ;
if ( sgt[ t ].l < sgt[ t ].r ) {
sgt[ left( t ) ].flag = sgt[ right( t ) ].flag = true ;
sgt[ left( t ) ].v = sgt[ right( t ) ].v = sgt[ t ].v ;
}
}
}

void update( int t ) {
pushdown( t ) ;
if ( sgt[ t ].l < sgt[ t ].r ) {
pushdown( left( t ) ) , pushdown( right( t ) ) ;
sgt[ t ].sum = sgt[ left( t ) ].sum + sgt[ right( t ) ].sum ;
sgt[ t ].maxl = max( sgt[ left( t ) ].maxl , sgt[ left( t ) ].sum + sgt[ right( t ) ].maxl ) ;
sgt[ t ].maxr = max( sgt[ right( t ) ].maxr , sgt[ right( t ) ].sum + sgt[ left( t ) ].maxr ) ;
sgt[ t ].maxs = max( max( sgt[ left( t ) ].maxs , sgt[ right( t ) ].maxs ) , sgt[ left( t ) ].maxr + sgt[ right( t ) ].maxl ) ;
}
}

state query( int l , int r , int t ) {
pushdown( t ) ;
if ( l == sgt[ t ].l && r == sgt[ t ].r ) return state( sgt[ t ].sum , sgt[ t ].maxs , sgt[ t ].maxl , sgt[ t ].maxr ) ;
int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
if ( r <= mid ) return query( l , r , left( t ) ) ;
if ( l > mid ) return query( l , r , right( t ) ) ;
return query( l , mid , left( t ) ) + query( mid + 1 , r , right( t ) ) ;
}

void change( int l , int r , int v , int t ) {
pushdown( t ) ;
if ( sgt[ t ].l == l && r == sgt[ t ].r ) {
sgt[ t ].flag = true , sgt[ t ].v = v ;
pushdown( t ) ;
return ;
}
int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
if ( r <= mid ) change( l , r , v , left( t ) ) ; else
if ( l > mid ) change( l , r , v , right( t ) ) ; else {
change( l , mid , v , left( t ) ) , change( mid + 1 , r , v , right( t ) ) ;
}
update( t ) ;
}

void build( int l , int r , int t ) {
sgt[ t ].l = l , sgt[ t ].r = r ;
if ( l == r ) {
sgt[ t ].sum = sgt[ t ].maxs = sgt[ t ].maxl = sgt[ t ].maxr = value[ arr[ l ] ] ;
return ;
}
int mid = ( l + r ) >> 1 ;
build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;
update( t ) ;
}

int Lca( int u , int v ) {
if ( h[ u ] < h[ v ] ) swap( u , v ) ;
for ( int i = 20 ; i >= 0 ; -- i ) {
if ( h[ up[ u ][ i ] ] >= h[ v ] ) {
u = up[ u ][ i ] ;
}
}
if ( u == v ) return u ;
for ( int i = 20 ; i >= 0 ; -- i ) {
if ( up[ u ][ i ] != up[ v ][ i ] ) {
u = up[ u ][ i ] , v = up[ v ][ i ] ;
}
}
return up[ u ][ 0 ] ;
}

state Query( int v , int u ) {
state ret ;
while ( h[ v ] >= h[ u ] ) {
if ( h[ first[ v ] ] > h[ u ] ) {
ret = query( num[ first[ v ] ] , num[ v ] , 1 ) + ret ;
v = up[ first[ v ] ][ 0 ] ;
} else {
ret = query( num[ u ] , num[ v ] , 1 ) + ret ;
break ;
}
}
return ret ;
}

void Change( int v , int u , int c ) {
while ( h[ v ] >= h[ u ] ) {
if ( h[ first[ v ] ] > h[ u ] ) {
change( num[ first[ v ] ] , num[ v ] , c , 1 ) ;
v = up[ first[ v ] ][ 0 ] ;
} else {
change( num[ u ] , num[ v ] , c , 1 ) ;
break ;
}
}
}

int main( ) {
memset( head , 0 , sizeof( head ) ) ;
scanf( "%d" , &n ) ;
for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , value + i ) ;
for ( int i = 1 ; i < n ; ++ i ) {
int s , t ; scanf( "%d%d" , &s , &t ) ;
AddEdge( s , t ) ;
}
memset( f , true , sizeof( f ) ) ;
h[ 1 ] = 1 ;
dfs0( 1 ) ;
memset( f , true , sizeof( f ) ) ;
dfs1( 1 , 1 ) ;
for ( int i = 1 ; i <= 20 ; ++ i ) {
for ( int j = 0 ; j ++ < n ; ) {
up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;
}
}
build( 1 , n , 1 ) ;
scanf( "%d" , &m ) ;
while ( m -- ) {
int x , u , v , c ; scanf( "%d%d%d" , &x , &u , &v ) ;
int lca = Lca( u , v ) ;
if ( x == 1 ) {
state l = Query( u , lca ) , r = Query( v , lca ) , M = Query( lca , lca ) ;
int ans = max( max( l.maxs , r.maxs ) , l.maxl + r.maxl - M.sum ) ;
printf( "%d " , ans ) ;
} else {
scanf( "%d" , &c ) ;
Change( u , lca , c ) , Change( v , lca , c ) ;
}
}
printf( "\n" ) ;
return 0 ;
}

表示树链剖分一时想不出怎么写，还是乖乖码LCT吧。。。

评测结果
VijosEx via libjudge

编译成功

测试数据 #0: Accepted, time = 31 ms, mem = 14912 KiB, score = 10

测试数据 #1: Accepted, time = 46 ms, mem = 14912 KiB, score = 10

测试数据 #2: Accepted, time = 46 ms, mem = 14912 KiB, score = 10

测试数据 #3: Accepted, time = 358 ms, mem = 15296 KiB, score = 10

测试数据 #4: Accepted, time = 390 ms, mem = 15296 KiB, score = 10

测试数据 #5: Accepted, time = 296 ms, mem = 15296 KiB, score = 10

测试数据 #6: Accepted, time = 468 ms, mem = 15296 KiB, score = 10

测试数据 #7: Accepted, time = 561 ms, mem = 15688 KiB, score = 10

测试数据 #8: Accepted, time = 842 ms, mem = 15684 KiB, score = 10

测试数据 #9: Accepted, time = 592 ms, mem = 15688 KiB, score = 10

Summary: Accepted, time = 3630 ms, mem = 15688 KiB, score = 100

{$M 10000000}
program park;
const inf=1000000000;
type tree=record
maxm,maxl,maxr,sum,lazy:longint;
flag:boolean
end;
var tr:array[0..400001] of tree;
E,pre:array[0..200001] of longint;
ft,dep,size,link,son,w,s,top,pot:array[0..100001] of longint;
xm,xl,xr,sum:array[1..2] of longint;
n,m,tot,L,maxm:longint;

function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b
end;

procedure add(a,b:longint);
begin
inc(L);
E[L]:=b;
pre[L]:=link[a];
link[a]:=L
end;

procedure dfs1(x,y:longint);
var maxi,k:longint;
begin
ft[x]:=y; dep[x]:=dep[y]+1; size[x]:=1;
k:=link[x]; maxi:=0;
while k<>0 do
begin
if E[k]<>ft[x] then
begin
dfs1(E[k],x);
size[x]:=size[x]+size[E[k]];
if size[E[k]]>size[maxi] then maxi:=E[k]
end;
k:=pre[k]
end;
son[x]:=maxi
end;

procedure dfs2(x,y:longint);
var k:longint;
begin
inc(tot); pot[x]:=tot; s[tot]:=w[x]; top[x]:=y;
if son[x]<>0 then dfs2(son[x],y);
k:=link[x];
while k<>0 do
begin
if (E[k]<>ft[x]) and (E[k]<>son[x]) then dfs2(E[k],E[k]);
k:=pre[k]
end
end;

procedure pushdown(k,L:longint);
var lc,rc,x:longint;
begin
lc:=k shl 1; rc:=lc+1; x:=tr[k].lazy;
if tr[k].lazy<0 then
begin
tr[lc].maxm:=x;
tr[rc].maxm:=x;
end
else
begin
tr[lc].maxm:=x*(L-L shr 1);
tr[rc].maxm:=x*(L shr 1)
end;
tr[lc].maxl:=tr[lc].maxm;
tr[lc].maxr:=tr[lc].maxm;
tr[rc].maxl:=tr[rc].maxm;
tr[rc].maxr:=tr[rc].maxm;
tr[lc].sum:=x*(L-L shr 1);
tr[rc].sum:=x*(L shr 1);
tr[lc].lazy:=x;
tr[rc].lazy:=x;
tr[lc].flag:=true;
tr[rc].flag:=true;
tr[k].flag:=false
end;

procedure update(k:longint);
var lc,rc:longint;
begin
lc:=k shl 1; rc:=lc+1;
tr[k].maxm:=max(tr[lc].maxr+tr[rc].maxl,max(tr[lc].maxm,tr[rc].maxm));
tr[k].maxl:=max(tr[lc].maxl,tr[lc].sum+tr[rc].maxl);
tr[k].maxr:=max(tr[rc].maxr,tr[rc].sum+tr[lc].maxr);
tr[k].sum:=tr[lc].sum+tr[rc].sum
end;

procedure build(low,high,k:longint);
var mid:longint;
begin
if low=high then
begin
tr[k].maxm:=s[low];
tr[k].maxl:=s[low];
tr[k].maxr:=s[low];
tr[k].sum:=s[low];
tr[k].flag:=false;
exit
end;
mid:=(low+high) shr 1;
build(low,mid,k shl 1);
build(mid+1,high,k shl 1+1);
update(k)
end;

procedure query(l,r,low,high,k,v:longint);
var mid:longint;
t1,t2,t3,t4:array[1..2] of longint;
begin
if (l=low) and (r=high) then
begin
xm[v]:=tr[k].maxm;
xl[v]:=tr[k].maxl;
xr[v]:=tr[k].maxr;
sum[v]:=tr[k].sum;
exit
end;
if tr[k].flag then pushdown(k,high-low+1);
mid:=(low+high) shr 1;
if r<=mid then
query(l,r,low,mid,k shl 1,v)
else
if mid<l then
query(l,r,mid+1,high,k shl 1+1,v)
else
begin
query(l,mid,low,mid,k shl 1,v);
t1[v]:=xm[v]; t2[v]:=xl[v]; t3[v]:=xr[v]; t4[v]:=sum[v];
query(mid+1,r,mid+1,high,k shl 1+1,v);
xm[v]:=max(t3[v]+xl[v],max(t1[v],xm[v]));
xl[v]:=max(t2[v],t4[v]+xl[v]);
xr[v]:=max(xr[v],sum[v]+t3[v]);
sum[v]:=t4[v]+sum[v]
end;
update(k)
end;

procedure find1(x,y:longint);
var t1,t2,t3,t4:array[1..2] of longint;
v:longint;
begin
xm[1]:=-inf; xl[1]:=-inf; xr[1]:=-inf; sum[1]:=0;
xm[2]:=-inf; xl[2]:=-inf; xr[2]:=-inf; sum[2]:=0;
t1[1]:=-inf; t2[1]:=-inf; t3[1]:=-inf; t4[1]:=0;
t1[2]:=-inf; t2[2]:=-inf; t3[2]:=-inf; t4[2]:=0;
while top[x]<>top[y] do
begin
if dep[top[x]]>dep[top[y]] then
begin
query(pot[top[x]],pot[x],1,n,1,1);
x:=ft[top[x]]; v:=1
end
else
begin
query(pot[top[y]],pot[y],1,n,1,2);
y:=ft[top[y]]; v:=2
end;
xm[v]:=max(t2[v]+xr[v],max(t1[v],xm[v]));
xl[v]:=max(xl[v],sum[v]+t2[v]);
xr[v]:=max(t3[v],t4[v]+xr[v]);
sum[v]:=t4[v]+sum[v];
t1[v]:=xm[v]; t2[v]:=xl[v]; t3[v]:=xr[v]; t4[v]:=sum[v]
end;
if dep[x]<dep[y] then
begin
query(pot[x],pot[y],1,n,1,2); v:=2
end
else
begin
query(pot[y],pot[x],1,n,1,1); v:=1
end;
xm[v]:=max(t2[v]+xr[v],max(t1[v],xm[v]));
xl[v]:=max(xl[v],sum[v]+t2[v]);
xr[v]:=max(t3[v],t4[v]+xr[v]);
sum[v]:=t4[v]+sum[v];
if (xm[1]=-inf) or (xm[2]=-inf) then maxm:=max(xm[1],xm[2])
else maxm:=max(xl[1]+xl[2],max(xm[1],xm[2]))
end;

procedure modify(l,r,x,low,high,k:longint);
var mid:longint;
begin
if (l=low) and (r=high) then
begin
L:=high-low+1;
if x<0 then
begin
tr[k].maxm:=x;
tr[k].maxl:=x;
tr[k].maxr:=x
end
else
begin
tr[k].maxm:=x*L;
tr[k].maxl:=x*L;
tr[k].maxr:=x*L
end;
tr[k].sum:=x*L;
tr[k].lazy:=x;
tr[k].flag:=true;
exit
end;
if tr[k].flag then pushdown(k,high-low+1);
mid:=(low+high) shr 1;
if r<=mid then
modify(l,r,x,low,mid,k shl 1)
else
if mid<l then
modify(l,r,x,mid+1,high,k shl 1+1)
else
begin
modify(l,mid,x,low,mid,k shl 1);
modify(mid+1,r,x,mid+1,high,k shl 1+1)
end;
update(k)
end;

procedure find2(x,y,c:longint);
begin
while top[x]<>top[y] do
if dep[top[x]]>dep[top[y]] then
begin
modify(pot[top[x]],pot[x],c,1,n,1);
x:=ft[top[x]]
end
else
begin
modify(pot[top[y]],pot[y],c,1,n,1);
y:=ft[top[y]]
end;
if dep[x]<dep[y] then modify(pot[x],pot[y],c,1,n,1)
else modify(pot[y],pot[x],c,1,n,1)
end;

procedure init;
var i,a,b,c,k:longint;
begin
L:=0; tot:=0;
readln(n);
for i:=1 to n do read(w[i]);
for i:=1 to n-1 do
begin
readln(a,b);
add(a,b);
add(b,a)
end;
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
readln(m);
for i:=1 to m do
begin
read(k);
if k=1 then
begin
readln(a,b);
find1(a,b);
if maxm<0 then write('0 ')
else write(maxm,' ')
end
else
begin
readln(a,b,c);
find2(a,b,c)
end
end
end;

begin
init
end.

线段树 ，上

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 541ms

├ 测试数据 06：答案正确... 619ms

├ 测试数据 07：答案正确... 666ms

├ 测试数据 08：答案正确... 1338ms

├ 测试数据 09：答案正确... 1478ms

├ 测试数据 10：答案正确... 1525ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：6167ms

速度比较慢，还得写非递归！～

递归会爆栈，202错误。

一开始, 总以为oimaster有一条链的数据...

呵呵, 结果没有!

可惜了, 第一次选错语言...不然就一次AC.

通过此题, 发现oimaster和CQF有惊人的相似.

CQF的棋盘上的士兵让人抓狂(我到现在还不敢写).

oimaster的小白让我呕心沥血2天...放弃了怪盗基德比赛打代码的啊!

就是树链剖分 + 线段树维护.

代码很烦!300行.

我在hi.baidu.com/boyzkk1里将会给出我的想法,

可能的话, 我还会贴出oimaster的代码.

//================VJ无敌bug, 状态里边的那个40分就是我的AC.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 447ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 306ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 759ms

├ 测试数据 09：答案正确... 759ms

├ 测试数据 10：答案正确... 791ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3062ms

jzp神牛不愧是我们江苏省队的骄傲啊，目前只有他AC了！

原来以为就是普通的小白加一个标记。。。

没想到它给改成树链剖分了。。。。。

orz

Heavy-Light-Decomposition

这个树链剖分是不是卡常数啊？标程都是卡过的。

原来时限是2S啊。不好意思没有注意到。

嘛是树链剖分？？本人对树可是一窍不通啊！