cqyz oj |【训练题】树的换根操作

Description

我们知道：N个点的无向图，满足下列三个条件中任意两个，那么就是一棵无根树：
(1)、连通；
(2)、有N-1条边；
(3)、任意两点有且仅有一条路径
我们也知道，一棵无根树中，任意一个点都可以作为根。现在的问题是，给出一棵含N个结点的无根树（结点编号为1..N），然后给出若干查询：query x y，其含义为：当以x为根时，y的父亲是谁（若无父亲，则输出0,，和以y为根的子树结点数量。

Input

第1行：包含两个整数N,M，分别表示树的结点数量和查询数量；　　接下来的N-1行，每行包含两个整数x,y，表示x和y之间有一条边连接；　　再接下来的M行，每行一条查询命令。

Output

包含M行，每行输出两个整数，表示查询结果

Sample Input 1

5 3
1 2
3 1
4 3
3 5
query 1 5
query 4 1
query 5 3

Sample Output 1

3 1
3 2
5 4

Hint

1<=n<=50000

核心换根操作，直接上代码

void flip(int x){//把x换成根 
    if(fa[x]){//若不是真正的树根 
        int y=fa[x];
        flip(y);//先把fa[x]换成根 
        //再把x换成根
        fa[x]=0;//默认根的父亲节点为0 
        fa[y]=x;
        siz[y]=n-siz[x];//换根后树y的节点数为除了树x上的点的数量 
        siz[x]=n; 
    }
}

该算法时间复杂度O(d)对于极端数据depth(x)=n时,和直接重新生成一棵以x为根的树O(n)时间复杂度相同，但是对于随机数据通常快得多。

完整代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 50005
#define maxm 100005
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
int fir[maxm],ne[maxm],to[maxm],np=0;
void add(int x,int y){
    ne[++np]=fir[x];
    fir[x]=np;
    to[np]=y;
}

int fa[maxn],siz[maxn];
int ans=0;
void dfs(int u){
    siz[u]=1;
    for(int i=fir[u];i;i=ne[i]){
        int v=to[i];
        if(v==fa[u])continue;
        
        fa[v]=u;
        dfs(v);
        siz[u]+=siz[v];
    }
}

int n,m;
void flip(int x){//把x换成根 
    if(fa[x]){//若不是真正的树根 
        int y=fa[x];
        flip(y);//先把fa[x]换成根 
        //再把x换成根
        fa[x]=0;//默认根的父亲节点为0 
        fa[y]=x;
        siz[y]=n-siz[x];//换根后树y的节点数为除了树x上的点的数量 
        siz[x]=n; 
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    fa[1]=0;
    dfs(1);
    
    char op[10];
    int x,y;
    while(m--){
        scanf("%s%d%d",op,&x,&y);
        flip(x);
        printf("%d %d\n",fa[y],siz[y]);
    }
    return 0;
}

优质内容筛选与推荐>>
1、8.5 Android灯光系统_源码分析_通知灯
2、常用正则表达式
3、读博有感
4、错误处理
5、expect实现自动分发密钥、网站度量术语