自动搬运

查看原文

来自洛谷，原作者为

	Lagrange_NoAria 光さえ 届かない瞳に何が映ろう 悪魔誘う 破滅だけ求めて 「もしも」が在ったのだろう その手に縋れたのなら 突き刺した紅は滲む 戾れない 世界で

搬运于2025-08-24 23:06:56，当前版本为作者最后更新于2024-12-14 12:06:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题选比较简单，把每个子节点的父亲记录下来，再计数每个节点的出入度。

然后对根节点计数，记为 $cnt$，并对此进行判断，输出第一组答案。
紧接着，对于每一次父子交换的操作，判断辈分情况，然后对 $cnt$ 进行修改，再次判断，输出。

代码如下：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n,m,u,v,cnt,ine[300005],oute[300005],father[300005];
int main(){
	cin>>n;
	for(int i = 1; i < n; i++){
		cin>>u>>v;
		father[v]=u;//u->v
		ine[u]++;oute[v]++;
	}
	for(int i = 1; i <= n; i++){
		if(oute[i]==0){
			cnt++;
		}
	}
	if(cnt==1) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
	cin>>m;
	for(int i = 1; i <= m; i++){
		cin>>u>>v;
		if(father[v]==u){//u--true--v
			father[u]=v;
			father[v]=0;
			if(++oute[u]==1) cnt--;
			if(--oute[v]==0) cnt++;
		}
		else{
			father[v]=u;
			father[u]=0;
			if(--oute[u]==0) cnt++;
			if(++oute[v]==1) cnt--;
		}
		if(cnt==1) cout<<"DA"<<endl;
		else cout<<"NE"<<endl; 
	}
	return 0;
}