[Codechef - AASHRAM] Gaithonde Leaves Aashram

Description

给出一棵树，树的“N”节点根植于节点1，每个节点‘u’与权重a[u]相关联。您还可以在树上执行两种类型的查询。查询的数量是‘M’。

1 U Val：对于类型1的查询，将给出一个节点‘U’和一个整数Val。设子树和=(包括‘U’)的子树中所有节点的权重之和。如果节点‘U’的子树之和为偶数，则将Val添加到‘U’的子树的每个节点(包括节点‘U’)，否则将1添加到子树的每个节点(包括节点‘U’)。
2 U-V：对于类型2的查询，将给出两个节点‘U’和‘V’，并且必须打印‘U’和‘V’的子树和的位XOR。

Solution

DFS序搞一下即可。

SB的我把主程序里DFS用反结果居然过了样例……

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000005;

namespace seg

{

int val[N],tag[N];

void pushup(int p)

{

    val[p]=val[p*2]+val[p*2+1];

}

void pushdown(int p,int l,int r)

{

    if(tag[p])

    {

        tag[p*2]+=tag[p];

        tag[p*2+1]+=tag[p];

        val[p*2]+=tag[p]*((l+r)/2-l+1);

        val[p*2+1]+=tag[p]*(r-(l+r)/2);

        tag[p]=0;

    }

}

void build(int p,int l,int r,int *src)

{

    if(l==r)

    {

        val[p]=src[l];

    }

    else

    {

        build(p*2,l,(l+r)/2,src);

        build(p*2+1,(l+r)/2+1,r,src);

        pushup(p);

    }

}

void modify(int p,int l,int r,int ql,int qr,int v)

{

    if(l>qr || r<ql)

        return;

    if(l>=ql && r<=qr)

    {

        val[p]+=v*(r-l+1);

        tag[p]+=v;

    }

    else

    {

        pushdown(p,l,r);

        modify(p*2,l,(l+r)/2,ql,qr,v);

        modify(p*2+1,(l+r)/2+1,r,ql,qr,v);

        pushup(p);

    }

}

int query(int p,int l,int r,int ql,int qr)

{

    if(l>qr || r<ql)

        return 0;

    if(l>=ql && r<=qr)

        return val[p];

    else

    {

        pushdown(p,l,r);

        return query(p*2,l,(l+r)/2,ql,qr) + query(p*2+1,(l+r)/2+1,r,ql,qr);

    }

}

}

namespace tree

{

vector <int> g[N];

int dfn[N],fin[N],vis[N],ind=0,n;

void link(int p,int q)

{

    g[p].push_back(q);

    g[q].push_back(p);

}

void dfs(int p)

{

    vis[p]=1;

    dfn[p]=++ind;

    for(int i=0; i<g[p].size(); i++)

    {

        if(vis[g[p][i]]==0)

        {

            dfs(g[p][i]);

        }

    }

    fin[p]=ind;

}

void presolve()

{

    memset(vis,0,sizeof vis);

    dfs(1);

}

int query(int p)

{

    return seg::query(1,1,n,dfn[p],fin[p]);

}

void modify(int p,int v)

{

    seg::modify(1,1,n,dfn[p],fin[p],v);

}

}

int n,m,t1,t2,t3,t4;

int v[N],src[N];

signed main()

{

    ios::sync_with_stdio(false);

    cin>>n>>m;

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

    {

        cin>>v[i];

    }

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

    {

        cin>>t1>>t2;

        tree::link(t1,t2);

    }

    tree::presolve();

    tree::n=n;

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

    {

        src[tree::dfn[i]]=v[i];

    }

    seg::build(1,1,n,src);

    for(int i=1; i<=m; i++)

    {

        cin>>t1>>t2>>t3;

        if(t1==1)

        {

            if(tree::query(t2)%2ll)

            {

                tree::modify(t2,1);

            }

            else

            {

                tree::modify(t2,t3);

            }

        }

        else

        {

            cout<<(tree::query(t2) ^ tree::query(t3))<<endl;

        }

    }

}

巴特西

[Codechef - AASHRAM] Gaithonde Leaves Aashram - 线段树,DFS序

[Codechef - AASHRAM] Gaithonde Leaves Aashram

Description

Solution

最新文章

热门文章