树链剖分【CF165D】Beard Graph

Description

给定一棵树，有m次操作。

1 x 把第x条边染成黑色

2 x 把第x条边染成白色

3 x y 查询x~y之间的黑边数，存在白边输出-1

Input

第1行为一个整数\(n\),表示有\(n\)个节点。

接下来\(n-1\)行描述一棵树。

第\(n+1\)行为一个整数\(m\)表示有\(m\)次操作。

接下来\(m\)行每行描述一个操作。

Output

对于每一个\(3\)操作输出一行。

一眼看到就能发现,这是一个树剖题,还是边权剖分。

需要注意的是边权转点权的时候,边权要赋值给较深的那个点,因为这样可以保证唯一性。

然后最终,轻重链交替跳转过程的最后,要注意应从\(dfn[x]+1,\)到\(dfn[y]\)

考虑我们当前点\(x\)接受的是哪条边的边权,但是现在查询过程中,是并没有涉及到这条边的。

我们记录白色边的权值为\(0\),黑色边的权值为\(1\),对于一段查询的区间,如果最小值为\(0\),那么就表明有白色边,输出\(-1\)即可。

否则查询区间和即可.(此时黑色边的边权为\(1\),这段区间的区间和就表示有多少条黑边。)

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define R register

using namespace std;

const int gz=1e5+8;

inline void in(R int &x)

{

	R int f=1;x=0;R char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int head[gz],tot,n,m;

struct cod{int u,v,fr;}edge[gz<<1];

inline void add(R int x,R int y)

{

    edge[++tot].u=head[x];

    edge[tot].fr=x;

    edge[tot].v=y;

    head[x]=tot;

}

int dfn[gz],idx,son[gz],f[gz],depth[gz],size[gz],top[gz];

void dfs1(R int u,R int fa)

{

    f[u]=fa;depth[u]=depth[fa]+1;size[u]=1;

    for(R int i=head[u];i;i=edge[i].u)

    {

        if(edge[i].v==fa)continue;

        dfs1(edge[i].v,u);

        size[u]+=size[edge[i].v];

        if(son[u]==-1 or size[son[u]]<size[edge[i].v])

            son[u]=edge[i].v;

    }

}

void dfs2(R int u,R int t)

{

    dfn[u]=++idx;top[u]=t;

    if(son[u]==-1)return ;

    dfs2(son[u],t);

    for(R int i=head[u];i;i=edge[i].u)

    {

        if(dfn[edge[i].v])continue;

        dfs2(edge[i].v,edge[i].v);

    }

}

int mn[gz<<2],tr[gz<<2];

#define ls o<<1

#define rs o<<1|1

inline void up(R int o)

{

	tr[o]=tr[ls]+tr[rs];

	mn[o]=min(mn[ls],mn[rs]);

}

void build(R int o,R int l,R int r)

{

	if(l==r)

	{

		tr[o]=mn[o]=1;

		return;

	}

	R int mid=(l+r)>>1;

	build(ls,l,mid);

	build(rs,mid+1,r);

	up(o);

}

void change(R int o,R int l,R int r,R int pos,R int k)

{

	if(l==r){tr[o]=mn[o]=k;return;}

	R int mid=(l+r)>>1;

	if(pos<=mid)change(ls,l,mid,pos,k);

	else change(rs,mid+1,r,pos,k);

	up(o);

}

int query_min(R int o,R int l,R int r,R int x,R int y)

{

	if(x<=l and y>=r)return mn[o];

	R int mid=(l+r)>>1,res=2147483647LL;

	if(x<=mid)res=min(res,query_min(ls,l,mid,x,y));

	if(y>mid)res=min(res,query_min(rs,mid+1,r,x,y));

	return res;

}

int query(R int o,R int l,R int r,R int x,R int y)

{

	if(x<=l and y>=r)return tr[o];

	R int mid=(l+r)>>1,res=0;

	if(x<=mid)res+=query(ls,l,mid,x,y);

	if(y>mid)res+=query(rs,mid+1,r,x,y);

	return res;

}

inline int tquery_min(R int x,R int y)

{

	R int fx=top[x],fy=top[y],res=2147483647LL;

	while(fx!=fy)

	{

		if(depth[fx]>depth[fy])

		{

			res=min(res,query_min(1,1,n,dfn[fx],dfn[x]));

			x=f[fx];

		}

		else

		{

			res=min(res,query_min(1,1,n,dfn[fy],dfn[y]));

			y=f[fy];

		}

		fx=top[x],fy=top[y];

	}

	if(x==y)return res;

	if(dfn[x]>dfn[y])swap(x,y);

	res=min(res,query_min(1,1,n,dfn[x]+1,dfn[y]));

	return res;

}

inline int tquery(R int x,R int y)

{

	R int fx=top[x],fy=top[y],res=0;

	while(fx!=fy)

	{

		if(depth[fx]>depth[fy])

		{

			res+=query(1,1,n,dfn[fx],dfn[x]);

			x=f[fx];

		}

		else

		{

			res+=query(1,1,n,dfn[fy],dfn[y]);

			y=f[fy];

		}

		fx=top[x],fy=top[y];

	}

	if(x==y)return res;

	if(dfn[x]>dfn[y])swap(x,y);

	res+=query(1,1,n,dfn[x]+1,dfn[y]);

	return res;

}

int main()

{

	in(n);memset(son,-1,sizeof son);

	for(R int i=1,x,y;i<n;i++)

		in(x),in(y),add(x,y),add(y,x);

	dfs1(1,0);dfs2(1,1);build(1,1,n);

	in(m);

	for(R int i=1,opt,x,y;i<=m;i++)

	{

		in(opt);

		if(opt==1)

		{

			in(x);x*=2;

            if(depth[edge[x].fr]>depth[edge[x].v])x=edge[x].fr;

            else x=edge[x].v;

            change(1,1,n,dfn[x],1);

		}

		if(opt==2)

		{

			in(x);x*=2;

            if(depth[edge[x].fr]>depth[edge[x].v])x=edge[x].fr;

            else x=edge[x].v;

            change(1,1,n,dfn[x],0);

		}

		if(opt==3)

		{

			in(x),in(y);

			if(tquery_min(x,y)==0)puts("-1");

			else printf("%d\n",tquery(x,y));

		}

	}

}

巴特西

树链剖分【CF165D】Beard Graph

Description

Input

Output

最新文章

热门文章