自动搬运

查看原文

来自洛谷，原作者为

	lory1608 历史经验告诉我们：人大多不会从历史经验中吸取教训

搬运于2025-08-24 22:24:28，当前版本为作者最后更新于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];
			}
		}
	}
}