CF342E 题解

bz02_2023f2

147人浏览 · 2026-07-01 21:22:28

bz02_2023f2 · 2026-07-01 21:22:28 发布

CF342E Xenia and Tree

题目描述

程序员 Xenia 有一棵包含 $n$ 个节点的树。我们假设这些树节点从 $1$ 到 $n$ 编号。最初，第一个节点被涂成红色，其余节点都被涂成蓝色。

两棵树上节点 $v$ 和 $u$ 之间的距离，指的是它们之间最短路径上经过的边的数量。

Xenia 需要快速地执行两种类型的操作：

将指定的蓝色节点染成红色；
查询给定节点距离最近的红色节点，并输出最短距离。

你的任务是编写一个程序，执行上述操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ $\leq n \leq 10^{5},\ 1 \leq m \leq 10^{5})$ —— 树的节点数和操作数。接下来 $n - 1$ 行每行两个整数 $a_i, b_i$ $\leq a_i, b_i \leq n, a_i \ne b_i)$ ，表示树中的一条边。

接下来的 $m$ 行，每行描述一个操作。每个操作包含两个整数 $t_i, v_i$ $\leq t_i \leq 2, 1 \leq v_i \leq n)$ 。如果 $t_i = 1$ ，则表示将编号 $v_i$ 的蓝色节点染成红色。如果 $t_i = 2$ ，则需要输出编号 $v_i$ 的节点到距离它最近的红色节点的最短距离。

保证给定的图是树，且所有的操作都是合法的。

输出格式

对于每个第二类型的操作，输出一行，表示最近红色节点到 $v_i$ 的最短距离。

输入输出样例 #1

输入 #1

输出 #1

0
3
2

说明/提示

由 ChatGPT 5 翻译

思路

分块即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,uu,vv,tt,f[100005][21],g[100005][21],de[100005],wd[100005],wec=0,oi=1e9+7,qs[100005];
struct one{
    long long t,v;
}u[100005];
struct two{
    long long a,v;
};
bool operator<(two a1,two b1){
    if(a1.v!=b1.v){
        return a1.v>b1.v;
    }
    else{
        return a1.a<b1.a;
    }
}
bool operator>(two a1,two b1){
    if(a1.v!=b1.v){
        return a1.v<b1.v;
    }
    else{
        return a1.a>b1.a;
    }
}
vector<long long> v[100005];
void abc(long long a1,long long b1){
    f[a1][0]=b1;
    g[a1][0]=1;
    de[a1]=de[b1]+1;
    for(int i=0;i<v[a1].size();i++){
        long long tt=v[a1][i];
        if(tt!=b1){
            abc(tt,a1);
        }
    }
    return ;
}
long long bcd(long long a1,long long b1){
    long long c1=0;
    if(de[b1]>=de[a1]){
        swap(a1,b1);
    }
    for(int i=20;i>=0;i--){
        if(de[f[a1][i]]>=de[b1]){
            c1+=g[a1][i];
            a1=f[a1][i];
        }
    }
    if(a1==b1){
        return c1;
    }
    else{
        for(int i=20;i>=0;i--){
            if(f[a1][i]!=f[b1][i]){
                c1+=g[a1][i];
                c1+=g[b1][i];
                a1=f[a1][i];
                b1=f[b1][i];
            }
        }
        return c1+2;
    }
}
priority_queue<two> q;
int main(){
    cin>>n>>m;
    wec=sqrt(m);
    for(int i=1;i<=n;i++){
        v[i].clear();
    }
    for(int i=1;i<=n;i++){
        wd[i]=1e9+7;
    }
    for(int i=1;i<=n-1;i++){
        cin>>uu>>vv;
        v[uu].push_back(vv);
        v[vv].push_back(uu);
    }
    abc(1,0);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
        }
    }
        for(int l=1;l<=n;l++){
            if(l==1){
                wd[1]=0;
                q.push({1,0});
            }
        }
        for(int l=1;l<=n;l++){
            qs[l]=0;
        }
        while(q.size()!=0){
            two a1=q.top();
            q.pop();
            if(qs[a1.a]==1){
                continue;
            }
            else{
                qs[a1.a]=1;
                for(int l=0;l<v[a1.a].size();l++){
                    long long tt=v[a1.a][l];
                    if(wd[tt]>=a1.v+1+1){
                        wd[tt]=a1.v+1;
                        q.push({tt,a1.v+1});
                    }
                }
            }
        }
    for(int i=1,j=1;i<=m;){
        j=1;
        for(int l=1;l<=wec;l++){
            u[l].t=0;
        }
        for(;j<=wec&&i<=m;j++){
            cin>>u[j].t>>u[j].v;
            i++;
        }
        for(int l=1;l<=j;l++){
            if(u[l].t==2){
                oi=wd[u[l].v];
                for(int r=1;r<=l-1;r++){
                    if(u[r].t==1){
                        oi=min(oi,bcd(u[l].v,u[r].v));
                    }
                }
                cout<<oi<<'\n';
            }
        }
        for(int l=1;l<=j;l++){
            if(u[l].t==1){
                wd[u[l].v]=0;
                q.push({u[l].v,0});
            }
        }
        for(int l=1;l<=n;l++){
            qs[l]=0;
        }
        while(q.size()!=0){
            two a1=q.top();
            q.pop();
            if(qs[a1.a]==1){
                continue;
            }
            else{
                qs[a1.a]=1;
                for(int l=0;l<v[a1.a].size();l++){
                    long long tt=v[a1.a][l];
                    if(wd[tt]>=a1.v+1+1){
                        wd[tt]=a1.v+1;
                        q.push({tt,a1.v+1});
                    }
                }
            }
        }
    }
	return 0;
}