题解 P6838 【[IOI2020]Stations】

lory1608 · 2020-09-24 18:05:49 · 题解

这道题比较奇怪，他会运行两次你的程序。

题意简述

给你一棵树，然后你需要给他重新标号，每次询问会给出一个你报好过的树上的起点s和终点t，以及起点的所有邻居，你需要返回s\to t的路径上的下一点是什么。

注意：你的主函数中不能存任何有用信息。

题解

你需要对所有点进行标号，那么我们考虑从一个跟开始，然后将其标为1000,然后对于每个点，如果他在奇数层，那么我们就先进行标号然后再向下给他的儿子标号，如果是偶数层，哦们先对他的儿子标号然后再给他标号。

这样对于每次询问。

• 起点为根，我们很轻易的知道从t在哪一个子树当中。
• 如果他在奇数层（此时邻居所有值都比他大），第一个子树中的点的编号为s+1\to num[son_{v_1}],第二个子树的点的编号为num[son_{1}]+1\to num[son_{2}],\cdots,最后一个子树m的编号为num_{son_{m-1}}+1\to num_{son_{m}}。
• 如果他在偶数层（此时邻居所有值都比他小），第一个子树中的点的编号为num[son_{v_1}]\to num[son_{v_2}]-1,第二个子树的点的编号为num[son_{v_2}]\to num[son_{v_3}]-1,\cdots,最后一个子树m的编号为num_{son_{m}}\to s-1。

这样就可以O(n^2)的通过这一题了。

确实一一道大思维题。

#include "stations.h"
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define REP(u) for(int i=p[u];i!=-1;i=e[i].nxt)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int maxn=1005;
vector<int>e[maxn];
vector<int>ans;
int cnt=-1;
inline void dfs(int u,int fa,int dep)
{
    if(dep%2==1)ans[u]=++cnt;
    for(int i=0;i<=(int)(e[u].size())-1;++i)
    {
        int v=e[u][i];
        if(v!=fa)
        {
            dfs(v,u,dep+1);
        }
    }
    if(dep%2==0)ans[u]=++cnt;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    ans.clear();
    FOR(i,0,n-1)ans.push_back(0); 
    FOR(i,0,n-1)e[i].clear();
    cnt=-1;
    FOR(i,0,n-2)
    {
        e[u[i]].push_back(v[i]);
        e[v[i]].push_back(u[i]);
    }
    dfs(0,0,0);
    ans[0]=1000;
    return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if((int)c.size()==1)return c[0];
    else
    {
        if(s==1000)
        {
            FOR(i,0,(int)(c.size())-2)
            {
                if(t>=c[i]&&t<c[i+1])return c[i];
            }
            return c[(int)c.size()-1];
        }
        else
        {
            if(s>c[(int)c.size()-1])///max
            {
                FOR(i,1,(int)(c.size())-2)
                {
                    if(t>=c[i]&&t<c[i+1])return c[i];
                }
                if(t>=c[(int)c.size()-1]&&t<s)return c[(int)c.size()-1];
                else return c[0];
            }
            else///min
            {
                if(t>s&&t<=c[0])return c[0];
                FOR(i,1,(int)(c.size())-2)
                {
                    if(t>c[i-1]&&t<=c[i])return c[i];
                }
                return c[(int)c.size()-1];
            }
        }
    }
}