Luogu P2590 [ZJOI2008]树的统计

最近在学树剖，看到了这题就做了

[ZJOI2008]树的统计

思路

　　从题面可以知道，这题是树剖题（要求的和模板没什么区别呀喂

　　就是在普通的树剖上加了一个最大值

　　所以可以知道就是树剖+特殊的线段树

　　线段树要可以求区间最大值和区间和

　　那么就很好做了，基本上就是到树剖模板题

　　只需要给线段树加个最大值就行了

实现

　　给线段树添加一个max，记录区间最大值

　　可以得到线段树结构体如下

struct Tree

{

    int max;

    int l,r;

    int lazy;

    int val;

}t[MAXN<<];

　　每次更改时更新max，val

　　由于只有单点修改，因此lazy tag可以不要

　　对于最大值，每次访问取两个区间的最大值

　　对于和，就和一般线段树一样了

　　求和代码如下

int query_sum(int x,int y,int p)

{

    if(x<=t[p].l&&t[p].r<=y)

        return t[p].val;

    int mid=(t[p].l+t[p].r)>>;

    int ans=;

    if(x<=mid)

        ans+=query_sum(x,y,p<<);

    if(y>mid)

        ans+=query_sum(x,y,p<<|);

    return ans;

}

　　求最大值代码如下

int query_max(int x,int y,int p)

{

    if(x<=t[p].l&&t[p].r<=y)

        return t[p].max;

    int mid=(t[p].l+t[p].r)>>;

    int ans=-1e9;

    if(x<=mid)

        ans=std::max(ans,query_max(x,y,p<<));

    if(y>mid)

        ans=std::max(ans,query_max(x,y,p<<|));

    return ans;

}

　　最后就是结合树剖了

代码

#include<bits/stdc++.h>

#define ll long long

using std::cin;

using std::cout;

using std::endl;

const int MAXN=3e4+;

struct Edge

{

    int to,next;

}e[MAXN<<];

struct Tree

{

    int max;

    int l,r;

    int lazy;

    int val;

}t[MAXN<<];

int son[MAXN],depth[MAXN],id[MAXN],num[MAXN],head[MAXN],pri[MAXN],size[MAXN],fa[MAXN],top[MAXN];

int cnt=;

void dfs1(int p,int f)

{

    depth[p]=depth[f]+;

    fa[p]=f;

    size[p]=;

    int now=head[p];

    while(now!=-)

    {

        if(e[now].to==f)

        {

            now=e[now].next;

            continue;

        }

        dfs1(e[now].to,p);

        size[p]+=size[e[now].to];

        if(son[p]==-||size[son[p]]<size[e[now].to])

            son[p]=e[now].to;

        now=e[now].next;

    }

}

void dfs2(int p,int t)

{

    top[p]=t;

    num[++cnt]=p;

    id[p]=cnt;

    if(son[p]==-)

        return;

    dfs2(son[p],t);

    int now=head[p];

    while(now!=-)

    {

        if(e[now].to==son[p]||e[now].to==fa[p])

        {

            now=e[now].next;

            continue;

        }

        dfs2(e[now].to,e[now].to);

        now=e[now].next;

    }

}

void build(int x,int y,int p)

{

    t[p].l=x;

    t[p].r=y;

    if(x==y)

    {

        t[p].val=pri[num[x]];

        t[p].max=pri[num[x]];

        return;

    }

    int mid=(x+y)>>;

    build(x,mid,p<<);

    build(mid+,y,p<<|);

    t[p].max=std::max(t[p<<].max,t[p<<|].max);

    t[p].val=t[p<<].val+t[p<<|].val;

}

void change(int u,int p,int w)

{

    if(t[p].l==u&&t[p].r==u)

    {

        t[p].val=w;

        t[p].max=w;

        return;

    }

    int mid=(t[p].l+t[p].r)>>;

    if(u<=mid)

        change(u,p<<,w);

    else

        change(u,p<<|,w);

    t[p].val=t[p<<].val+t[p<<|].val;

    t[p].max=std::max(t[p<<].max,t[p<<|].max);

}

int query_max(int x,int y,int p)

{

    if(x<=t[p].l&&t[p].r<=y)

        return t[p].max;

    int mid=(t[p].l+t[p].r)>>;

    int ans=-1e9;

    if(x<=mid)

        ans=std::max(ans,query_max(x,y,p<<));

    if(y>mid)

        ans=std::max(ans,query_max(x,y,p<<|));

    return ans;

}

int query_sum(int x,int y,int p)

{

    if(x<=t[p].l&&t[p].r<=y)

        return t[p].val;

    int mid=(t[p].l+t[p].r)>>;

    int ans=;

    if(x<=mid)

        ans+=query_sum(x,y,p<<);

    if(y>mid)

        ans+=query_sum(x,y,p<<|);

    return ans;

}

int qmax(int x,int y)

{

    int ans=-1e9;

    while(top[x]!=top[y])

    {

        if(depth[top[x]]<depth[top[y]])

            std::swap(x,y);

        ans=std::max(ans,query_max(id[top[x]],id[x],));

        x=fa[top[x]];

    }

    if(id[x]>id[y])

        std::swap(x,y);

    ans=std::max(ans,query_max(id[x],id[y],));

    return ans;

}

int qsum(int x,int y)

{

    int ans=;

    while(top[x]!=top[y])

    {

        if(depth[top[x]]<depth[top[y]])

            std::swap(x,y);

        ans+=query_sum(id[top[x]],id[x],);

        x=fa[top[x]];

    }

    if(id[x]>id[y])

        std::swap(x,y);

    ans+=query_sum(id[x],id[y],);

    return ans;

}

int main()

{

    std::ios::sync_with_stdio(false);

    memset(head,-,sizeof(head));

    memset(son,-,sizeof(son));

    int n;

    cin>>n;

    for(int i=;i<*(n-);i++)

    {

        int a,b;

        cin>>a>>b;

        e[i].to=b;

        e[i].next=head[a];

        head[a]=i++;

        e[i].to=a;

        e[i].next=head[b];

        head[b]=i;

    }

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

        cin>>pri[i];

    int q;

    cin>>q;

    dfs1(,);

    cnt=;

    dfs2(,);

    build(,n,);

    for(int i=;i<q;i++)

    {

        std::string op;

        cin>>op;

        if(op=="CHANGE")

        {

            int u,v;

            cin>>u>>v;

            change(id[u],,v);

        }

        if(op=="QMAX")

        {

            int u,v;

            cin>>u>>v;

            printf("%d\n",qmax(u,v));

        }

        if(op=="QSUM")

        {

            int u,v;

            cin>>u>>v;

            printf("%d\n",qsum(u,v));

        }

    }

    system("pause");//上交oj时记得注释或删除

    return ;

}

　　附带Luogu评测结果

　　不知道为什么除了对于操作符使用了cin其他都是scanf和printf的在一本通oj上TLE了……

　　于是就换成了取消同步的cin cout

巴特西

Luogu P2590 [ZJOI2008]树的统计

思路

实现

代码

最新文章

热门文章