[Codechef - ADITREE] Adi and the Tree - 树链剖分,线段树

[Codechef - ADITREE] Adi and the Tree

Description

树上每个节点有一个灯泡，开始所有灯泡都是熄灭的。每次操作给定两个数 \(a,b\) ，将 \(a,b\) 这两个节点的灯的状态改变。定义某个状态的权值为，将树上所有亮点两两配对，每个对的权值的总和最小值。其中一个配对的权值定义为这两个点之间的距离。求出每次操作后的权值。

Solution

很容易发现如果我们将每个亮点到树根的路径染色，那么染色次数为奇数的路径就会被统计入答案。

所以只需要维护布尔值就可以，这样每次操作就转化为对点到根的路径异或，询问就是整棵树的权和。树链剖分一下就可以。

#include <bits/stdc++.h>

using namespace std;

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]^=1;

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

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

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

        tag[p]^=1;

    }

}

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

{

    if(l>qr || r<ql)

        return ;

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

    {

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

        tag[p]^=1;

    }

    else

    {

        pushdown(p,l,r);

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

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

        pushup(p);

    }

}

int query()

{

    return val[1];

}

} // seg

namespace tree

{

vector <int> g[N];

int n,top[N],wson[N],siz[N],dep[N],vis[N],tid[N],did[N],fa[N],cnt=0;

void link(int p,int q)

{

    g[p].push_back(q);

    g[q].push_back(p);

}

void dfs1(int p)

{

    vis[p]=siz[p]=1;

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

    {

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

        {

            dep[g[p][i]]=dep[p]+1;

            fa[g[p][i]]=p;

            dfs1(g[p][i]);

            siz[p]+=siz[g[p][i]];

            if(wson[p]==0 || siz[g[p][i]]>siz[wson[p]])

                wson[p]=g[p][i];

        }

    }

}

void dfs2(int p)

{

    vis[p]=1;

    did[p]=++cnt;

    tid[cnt]=p;

    if(wson[p])

    {

        top[wson[p]]=top[p];

        dfs2(wson[p]);

    }

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

    {

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

        {

            top[g[p][i]]=g[p][i];

            dfs2(g[p][i]);

        }

    }

}

void presolve()

{

    dep[1]=1;

    dfs1(1);

    memset(vis,0,sizeof vis);

    top[1]=1;

    dfs2(1);

}

void link_modify(int p,int q)

{

    while(top[p]-top[q])

    {

        if(dep[top[p]]>dep[top[q]])

            swap(p,q);

        seg::modify(1,1,n,did[top[q]],did[q]);

        q=fa[top[q]];

    }

    if(dep[p]>dep[q])

        swap(p,q);

    seg::modify(1,1,n,did[p],did[q]);

}

}

int n,m,t1,t2,t3;

int main()

{

    scanf("%d",&n);

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

    {

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

        tree::link(t1,t2);

    }

    tree::n=n;

    tree::presolve();

    scanf("%d",&m);

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

    {

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

        tree::link_modify(1,t1);

        tree::link_modify(1,t2);

        printf("%d\n",seg::query());

    }

}

巴特西

[Codechef - ADITREE] Adi and the Tree - 树链剖分,线段树

[Codechef - ADITREE] Adi and the Tree

Description

Solution

最新文章

热门文章