Tourism on Mars URAL – 2109(LCA+线段树)

题目链接:https://cn.vjudge.net/problem/URAL-2109
评测机有毒,,,特判了n==1的情况然后没有return 0导致后面的输入没有数据输入,,然后返回了一天的re,你好歹返回个TLE我也知道上哪改啊emmm
题目大意:有一颗以1为根的树,给出若干查询l,r要从l到l+1,l+1到l+2…一直到r,问这个过程中距离根最近的点的编号
解题思路:lca+线段树,线段树的叶子节点存储i到i+1的lca,然后上层节点存储距离根的距离并维护这个区间内距离根最短的节点的编号
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int v,next;
} edge[500005];
struct Tree
{
    int l,r,data,deep;
} tree[1000010];
int head[200005],deep[200002],fa[200020][22];
long long lg[500050];
int vis[200002],dis[200020];
int cnt=0;
int minn,ans;

void add(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs(int f,int fath)
{
    deep[f]=deep[fath]+1;
    fa[f][0]=fath;
    for(int i=1; (1<<i)<=deep[f]; i++)
        fa[f][i]=fa[fa[f][i-1]][i-1];
    for(int i=head[f]; i!=-1; i=edge[i].next)
    {
        if(edge[i].v!=fath)
        {
            dfs(edge[i].v,f);
        }
    }
}

int lca(int x,int y)
{
    if(deep[x]<deep[y])
    {
        swap(x,y);
    }
    while(deep[x]>deep[y])
    {
        x=fa[x][lg[deep[x]-deep[y]]-1];
    }
    if(x==y)
    {
        return x;
    }
    for(int k=lg[deep[x]]; k>=0; k--)
    {
        if(fa[x][k]!=fa[y][k])
        {
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}

void build(int root,int l,int r)
{
    tree[root].l=l;
    tree[root].r=r;
    if(l==r)
    {
        tree[root].data=lca(l,l+1);
        tree[root].deep=deep[tree[root].data];
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    if(tree[root<<1].deep<tree[root<<1|1].deep)
    {
        tree[root].deep=tree[root<<1].deep;
        tree[root].data=tree[root<<1].data;
    }
    else
    {
        tree[root].deep=tree[root<<1|1].deep;
        tree[root].data=tree[root<<1|1].data;
    }
}

void query(int root,int l,int r)
{
    if(tree[root].l>=l&&tree[root].r<=r)
    {
        if(tree[root].deep<minn)
        {
            minn=tree[root].deep;
            ans=tree[root].data;
        }
        return;
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(l<=mid)
        query(root<<1,l,r);
    if(r>mid)
        query(root<<1|1,l,r);
}

int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    int n,q;
    int l,r;
    cin>>n;
    if(n==1)
    {
        cin>>q;
        while(q--)
        {
            cin>>l>>r;
            cout<<"1"<<endl;
        }
        return 0;
    }
    int u,v;
    cnt=0;
    for(int i=1; i<n; i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(long long i=1; i<=n; i++)
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    build(1,1,n-1);
    cin>>q;
    while(q--)
    {
        minn=0x3f3f3f3f;
        cin>>l>>r;
        if(l==r)
        {
            cout<<l<<endl;
        }
        else
        {
            query(1,l,r-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注