CF1278E Tests for problem D 题解

skyskyCCC · 2023-12-17 16:21:42 · 题解

前言。

本题的精华在于题目中“构造 n 个区间”这句话，鲜明地表达了本题的算法：构造。所以我们它的正确性就不用考虑了，我们只关心如何构造。

分析。

考虑维护一个链表。开始时我们让第 1 号结点为根结点，并把第 1 号结点的所代表的区间的两个端点插入链表。然后从第 1 号结点开始进行搜索。每遍历到一个新结点，就把它所代表的区间的左端点插入它父亲所代表的区间的右端点的左边，再把它所代表的区间的右端点插入它父亲所代表的线段的右端点的右边，可以简单理解为合并两个区间，最后遍历整个链表，给每个区间的端点分配一个下标，随后输出。

时间复杂度 O\left(n\right) 绰绰有余。

代码如下，仅供参考：

#include<iostream>
using namespace std;
int n,v,u;
struct node{
    int l,r;
}a[500005*2],ans[500005];
struct edge{
    int nex,to;
}b[500005*2];
int head[500005];
int sum,c=2,countt=0;
void add_edge(int u,int v){
    b[c].to=v;
    b[c].nex=head[u];
    head[u]=c++;
}
void build(int son,int fa){
    int left=a[fa<<1|1].l,right=a[fa<<1|1].r;
    a[left].r=son<<1;
    a[right].l=son<<1|1;
    a[son<<1].l=left;
    a[son<<1].r=fa<<1|1;
    a[fa<<1|1].l=son<<1;
    a[fa<<1|1].r=son<<1|1;
    a[son<<1|1].l=fa<<1|1;
    a[son<<1|1].r=right;
}
void dfs(int id,int fa){
    if(fa!=0){
        build(id,fa);
    }
    for(int i=head[id];i;i=b[i].nex){
        if(b[i].to==fa){
            continue;
        }
        dfs(b[i].to,id);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    a[1<<1].r=1<<1|1;
    a[1<<1|1].l=1<<1;
    dfs(1,0);
    for(int i=2;i<=(n<<1|1);i++){
        if(a[i].l==0){
            sum=i;
            break;
        }
    }
    while(a[sum].r!=0){
        countt++;
        if(sum%2==1){
            ans[sum>>1].r=countt;
        }
        else{
            ans[sum>>1].l=countt;
        }
        sum=a[sum].r;
    }
    if(sum%2==1){
        ans[sum>>1].r=countt+1;
    }
    else{
        ans[sum>>1].l=countt+1;
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i].l<<" "<<ans[i].r<<"\n";
    }
    long long isejr=0;
    return 0;
}

后记。

大家如有疑问，可以在评论区提出，我会尽力解答的。