[题解] 洛谷P3950 部落冲突

传送门

拿到题目，一看 裸LCT （其实是我懒得打，splay又臭又长）

首先，这道题的意思就是删掉一些边

所以常规操作点权转边权

之后对于战争操作，在对应的边上+1

对于和平操作，在对应的边上-1

然后对于询问，即统计从\(u\)到\(v\)的路径上的和

如果和为\(0\)，即表明可以到，否则不能到

代码



#include<bits/stdc++.h>

namespace my_std

{

	using namespace std;

	#define rep(i,a,b) for (int i=(a);i<=(b);i++)

	#define drep(i,a,b) for (int i=(a);i>=(b);i--)

	#define go(u) for (int i=head[(u)];i;i=e[i].nxt)

	#define pf printf

	#define writeln(x) write(x),putchar('\n')

	#define writesp(x) write(x),putchar(' ')

	#define mem(x,v) memset(x,v,sizeof(x))

	typedef long long ll;

	const int INF=0x7fffffff;

	inline int read()

	{

		int sum=0,f=1;

		char c=0;

		while (!isdigit(c))

		{

			if (c=='-') f=-1;

			c=getchar();

		}

		while (isdigit(c))

		{

			sum=(sum<<1)+(sum<<3)+(c^48);

			c=getchar();

		}

		return sum*f;

	}

	void write(int k)

	{

		if (k<0) putchar('-'),k=-k;

		if (k>=10) write(k/10);

		putchar(k%10+'0');

	}

}

using namespace my_std;

const int N=300010;

int n,quiz,cnt,tree[N],head[N];

int son[N],top[N],size[N];

int idx,in[N],num[N],f[N],dep[N];

struct edge

{

	int to,nxt;

}e[N<<1];

struct node

{

	int x,y;

}a[N];

#define lowbit(x) (x&(-x))

void update(int x,int y)

{

	while (x<=n)

	{

		tree[x]+=y;

		x+=lowbit(x);

	}

}

int getsum(int x)

{

	int res=0;

	while (x>0)

	{

		res+=tree[x];

		x-=lowbit(x);

	}

	return res;

}

int query(int l,int r)

{

	return getsum(r)-getsum(l-1);

}

void add(int u,int v)

{

	e[++cnt].to=v;

	e[cnt].nxt=head[u];

	head[u]=cnt;

}

void dfs1(int u,int fa)

{

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

	f[u]=fa;

	size[u]=1;

	go(u)

	{

		int v=e[i].to;

		if (v==fa) continue;

		dfs1(v,u);

		size[u]+=size[v];

		if (size[son[u]]<size[v])

		{

			son[u]=v;

		}

	}

}

void dfs2(int u,int t)

{

	in[u]=++idx;

	num[idx]=u;

	top[u]=t;

	if (son[u]==0) return;

	dfs2(son[u],t);

	go(u)

	{

		int v=e[i].to;

		if (v==f[u]||v==son[u]) continue;

		dfs2(v,v);

	}

}

int query_tree(int x,int y)

{

	int res=0;

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

	{

		if (dep[top[x]]<dep[top[y]]) swap(x,y);

		res+=query(in[top[x]],in[x]);

		x=f[top[x]];

	}

	if (dep[x]<dep[y]) swap(x,y);

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

	return res;

}

int main()

{

	n=read(),quiz=read();

	int u,v;

	rep(i,1,n-1)

	{

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

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

	}

	dfs1(1,0);

	dfs2(1,1);

	char opt;

	int p,q;

	cnt=0;

	rep(i,1,quiz)

	{

		scanf("%s",&opt);

		if (opt=='Q')

		{

			p=read(),q=read();

			int res=query_tree(p,q);

			if (res==0) pf ("Yes\n");

			else pf ("No\n");

		}

		if (opt=='C')

		{

			p=read(),q=read();

			if (dep[p]<dep[q]) swap(p,q);

			update(in[p],1);

			a[++cnt].x=p;

			a[cnt].y=q;

		}

		if (opt=='U')

		{

			p=read();

			update(in[a[p].x],-1);

		}

	}

}

巴特西

[题解] 洛谷P3950 部落冲突

最新文章

热门文章