luogu P4116 Qtree3

题目描述

给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白

有两种操作：

0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）

1 v : 询问1到v的路径上的第一个黑点，若无，输出-1

输入格式

第一行 N，Q，表示N个点和Q个操作

第二行到第N行N-1条无向边

再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).

输出格式

对每个1 v操作输出结果

考虑只对于一条到根的路径的情况：

如果给路径加了一个黑点，那么有两种情况：一是这个黑点深度不是最小的，那么我们不用管它；二是这个黑点是深度最小的黑点，那么我们需要对这条路径的信息进行更新。如果给路径删了一个黑点的话类似。

所以对于一条路径的情况，我们需要一个支持维护最小值、加入和删除点的数据结构。那么堆可以胜任。

那么考虑完整的树的情况：

不难想到对于每个点到根节点的路径都维护一个堆，那么一共要维护N个堆，每次修改最多改N个点的信息(树为一条链，修改根节点)。复杂度显然是我们不能接受的。

由于树链剖分之后每一条路径都可以表示成几个链子拼起来的形式，所以我们可以对原树进行重链剖分。然后我们只需要对于每条链子都维护一个堆即可。

时间复杂度为O(NlogNlogN)

#include<iostream>

#include<cstring>

#include<cstdio>

#include<set>

#define maxn 100001

#define maxm 300001

using namespace std;

int n,m;

bool col[maxn];

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

struct edge{

    int to,next;

    edge(){}

    edge(const int &_to,const int &_next){ to=_to,next=_next; }

}e[maxn<<1];

int head[maxn],k;

inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]),head[u]=k++; }

int size[maxn],dep[maxn],fa[maxn],son[maxn];

int dfn[maxn],id[maxn],top[maxn],tot;

void dfs_getson(int u){

    size[u]=1;

    for(register int i=head[u];~i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[u]) continue;

        fa[v]=u,dep[v]=dep[u]+1;

        dfs_getson(v),size[u]+=size[v];

        if(size[v]>size[son[u]]) son[u]=v;

    }

}

void dfs_rewrite(int u,int tp){

    dfn[u]=++tot,id[tot]=u,top[u]=tp;

    if(son[u]) dfs_rewrite(son[u],tp);

    for(register int i=head[u];~i;i=e[i].next){

        int v=e[i].to;

        if(v!=fa[u]&&v!=son[u]) dfs_rewrite(v,v);

    }

}

set<int> ans[maxn];

int main(){

    memset(head,-1,sizeof head);

    n=read(),m=read();

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

        int u=read(),v=read();

        add(u,v),add(v,u);

    }

    dfs_getson(1),dfs_rewrite(1,1);

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

        int op=read(),u=read();

        if(op==0){

            col[u]^=1;

            if(col[u]) ans[top[u]].insert(dfn[u]);

            else ans[top[u]].erase(dfn[u]);

        }else{

        	int v=0x3f3f3f3f,k;

        	while(top[u]!=1){

        		k=*ans[top[u]].begin();

        		if(ans[top[u]].size() && dep[id[k]]<=dep[u]) v=id[k];

        		u=fa[top[u]];

        	}

        	k=*ans[1].begin();

        	if(ans[1].size() && dep[id[k]]<=dep[u]) v=id[k];

        	printf("%d\n",v==0x3f3f3f3f?-1:v);

        }

    }

    return 0;

}

巴特西

luogu P4116 Qtree3

题目描述

给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白

有两种操作：

0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）

1 v : 询问1到v的路径上的第一个黑点，若无，输出-1

输入格式

第一行 N，Q，表示N个点和Q个操作

第二行到第N行N-1条无向边

再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).

输出格式

对每个1 v操作输出结果

考虑只对于一条到根的路径的情况：

如果给路径加了一个黑点，那么有两种情况：一是这个黑点深度不是最小的，那么我们不用管它；二是这个黑点是深度最小的黑点，那么我们需要对这条路径的信息进行更新。如果给路径删了一个黑点的话类似。

所以对于一条路径的情况，我们需要一个支持维护最小值、加入和删除点的数据结构。那么堆可以胜任。

那么考虑完整的树的情况：

不难想到对于每个点到根节点的路径都维护一个堆，那么一共要维护N个堆，每次修改最多改N个点的信息(树为一条链，修改根节点)。复杂度显然是我们不能接受的。

由于树链剖分之后每一条路径都可以表示成几个链子拼起来的形式，所以我们可以对原树进行重链剖分。然后我们只需要对于每条链子都维护一个堆即可。

时间复杂度为O(NlogNlogN)

最新文章

热门文章