小白逛公园加强版(park)

题目描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦……在小新家附近有n个公园，这些公园通过一些路径相连，并保证每两个公园之间有且仅有一条通路相连（也就是说这是一棵树），小白早就看花了眼，自己也不清楚该去哪些公园玩了。

小白对每个公园都有一个评价（可正可负），并且它只会让小新做两件事：

1. 询问公园a到公园b路径上最大连续公园的评价和，就是说我们把公园a到公园b路径上的公园（包括a和b）排成一条直线，那么小白希望知道一段连续的公园的评价和最大为多少。

2. 修改公园a到公园b路径上（包括a和b）每个公园的评价值。

小新现在已经处理不了n超过10的情况，因此请你来帮忙……

输入

第一行有一个自然数，表示n

第二行有n个自然数，表示一开始小白对每个公园的评价（评价值的绝对值不超过10000）

下面有n-1行，每行两个数a和b，表示公园a和公园b直接由道路相连

再下面一行有一个自然数，表示m

最后m行，每行第一个数k表示要执行的操作。如果k为1，那么后面有两个自然数a和b，表示询问公园a到公园b路径上（包含a和b）最大的连续公园评价和（如果这条路径上每个公园的评价都为负数，那么最大连续和为0）。如果k为2，那么后面有三个自然数a、b和c，表示把公园a到公园b路径上所有的公园（包括a和b）的评价都修改为c。（c的绝对值不超过10000）

输出

对于每次询问，输出最大连续和。（每行一个）

样例输入

5

-3 -2 1 2 3

1 2

2 3

1 4

4 5

3

1 2 5

2 3 4 2

1 2 5

样例输出

5

9

提示

对于30%的数据：n,m <= 100

对于70%的数据：n,m <= 50000

对于100%的数据：n,m <= 100000

solution

先写个树剖，转化为区间问题。

考虑如何求一段区间权值和最大的连续子序列

在线段树中记

lm：从左开始的最大值

rm：从右开始的最大值

x：中间的最大值（包括两边）

sum：和

这样就可以维护了

void wh(int k){

    tree[k].lm=max(tree[k*2].lm,tree[k*2].sum+tree[k*2+1].lm);

    tree[k].rm=max(tree[k*2+1].rm,tree[k*2+1].sum+tree[k*2].rm);

    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;

    tree[k].x=max(max(tree[k*2].x,tree[k*2+1].x),tree[k*2].rm+tree[k*2+1].lm);

}

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 100005

#define inf 1e9

using namespace std;

int n,m,head[maxn],son[maxn],fa[maxn],size[maxn],top[maxn],deep[maxn];

int dfn[maxn],dy[maxn],sc,t1,t2,tot,w[maxn],op,a,b,c,li,ri,ans;

struct node{

    int lm,rm,x,sum,l,r;

    int bj;

}tree[maxn*4],ansa,ansb;

struct no{

    int v,nex;

}e[maxn*2];

void lj(int t1,int t2){

    tot++;e[tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;

}

void dfs1(int k,int fath){

    fa[k]=fath;deep[k]=deep[fath]+1;

    int gp=-1,sz=0;

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v!=fath){

            dfs1(e[i].v,k);

            sz+=size[e[i].v];

            if(gp==-1)gp=e[i].v;

            if(size[e[i].v]>size[gp])gp=e[i].v;

        }

    }

    size[k]=sz+1;son[k]=gp;

}

void dfs2(int k){

    dfn[k]=++sc;dy[sc]=k;

    if(son[k]!=-1)top[son[k]]=top[k],dfs2(son[k]);

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v!=fa[k]&&e[i].v!=son[k]){

            top[e[i].v]=e[i].v;

            dfs2(e[i].v);

        }

    }

}

void wh(int k){

    tree[k].lm=max(tree[k*2].lm,tree[k*2].sum+tree[k*2+1].lm);

    tree[k].rm=max(tree[k*2+1].rm,tree[k*2+1].sum+tree[k*2].rm);

    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;

    tree[k].x=max(max(tree[k*2].x,tree[k*2+1].x),tree[k*2].rm+tree[k*2+1].lm);

}

void update(int k,int v){

    tree[k].sum=(tree[k].r-tree[k].l+1)*v;

    if(tree[k].sum<0)tree[k].x=tree[k].lm=tree[k].rm=0;

    else tree[k].x=tree[k].lm=tree[k].rm=tree[k].sum;

}

void build(int k,int L,int R){

    tree[k].l=L,tree[k].r=R;tree[k].bj=-inf;

    if(L==R){

        update(k,w[dy[L]]);

        return;

    }

    int mid=L+R>>1;

    build(k*2,L,mid);build(k*2+1,mid+1,R);

    wh(k);

}

node hb(node a,node b){

    node t;

    t.lm=max(a.lm,a.sum+b.lm);

    t.rm=max(b.rm,b.sum+a.rm);

    t.sum=a.sum+b.sum;

    t.x=max(max(a.x,b.x),a.rm+b.lm);

    return t;

}

void down(int k){

    if(tree[k].bj!=-inf){

        tree[k*2].bj=tree[k*2+1].bj=tree[k].bj;

        update(k*2,tree[k].bj);

        update(k*2+1,tree[k].bj);

        tree[k].bj=-inf;

    }

}

node ask(int k){

    if(tree[k].l>=li&&tree[k].r<=ri){

        return tree[k];

    }

    down(k);

    int mid=tree[k].l+tree[k].r>>1;

    node now;now.x=-1e9;now.lm=now.rm=now.sum=0;

    if(li<=mid)now=ask(k*2);

    if(ri>mid)now=hb(now,ask(k*2+1));

    return now;

}

void lian(int k){

    if(tree[k].l>=li&&tree[k].r<=ri){

        update(k,c);tree[k].bj=c;

        return;

    }

    down(k);

    int mid=tree[k].l+tree[k].r>>1;

    if(li<=mid)lian(k*2);

    if(ri>mid)lian(k*2+1);

    wh(k);

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    for(int i=1;i<n;i++){

        scanf("%d%d",&t1,&t2);

        lj(t1,t2);lj(t2,t1);

    }

    dfs1(1,0);top[1]=1;dfs2(1);

    build(1,1,n);

    cin>>m;

    while(m--){

        scanf("%d",&op);

        if(op==1){

            scanf("%d%d",&a,&b);

            t1=top[a],t2=top[b];

            ansa.x=-1e9;ansa.lm=ansa.rm=ansa.sum=0;

            ansb.x=-1e9;ansb.lm=ansb.rm=ansb.sum=0;

            while(t1!=t2){

                if(deep[t1]>=deep[t2]){

                    li=dfn[t1],ri=dfn[a];

                    ansa=hb(ask(1),ansa);

                    a=fa[t1];t1=top[a];

                }

                else {

                    li=dfn[t2],ri=dfn[b];

                    ansb=hb(ask(1),ansb);

                    b=fa[t2];t2=top[b];

                }

            }

            if(deep[a]<deep[b]){

                li=dfn[a],ri=dfn[b];

                ansb=hb(ask(1),ansb);

            }

            else {

                li=dfn[b],ri=dfn[a];

                ansa=hb(ask(1),ansa);

            }

            ans=max(ansa.x,ansb.x);

            ans=max(ans,ansa.lm+ansb.lm);

            printf("%d\n",max(ans,0));

        }

        else{

        scanf("%d%d%d",&a,&b,&c);

            t1=top[a],t2=top[b];

            while(t1!=t2){

                if(deep[t1]<deep[t2])swap(t1,t2),swap(a,b);

                li=dfn[t1],ri=dfn[a];

                lian(1);

                a=fa[t1],t1=top[a];

            }

            if(deep[a]<deep[b])swap(a,b);

            li=dfn[b],ri=dfn[a];

            lian(1);

        }

    }

    return 0;

}

巴特西

小白逛公园加强版(park)