题解：P11389 [COCI 2024/2025 #1] 等级 / Hijerarhija

Lagrange_NoAria · 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;
}