CodeForces 1340D Nastya and Time Machine
https://codeforces.com/contest/1340/problem/D
\(n\) 个城市形成了一个树的结构,通过每个道路需要单位 \(1\) 的时间,Nastya想要从 \(1\) 节点出发,访问每个节点至少一次后,回到 \(1\) 节点.
Nastya有一台时间机器,它可以在一个节点跳回到任意一个过去的时间.但是由于宇宙法则,不能有两个Nastya在同一时间存在与同一城市.
也就是说,需要找到一个序列 \(\{u_1,t_1\},\{u_2,t_2\},\cdots,\{u_k,t_k\}\) ,满足
- \(u_1=1,t_1=0\) , \(u_k=1\) .
- \(1,2,\cdots,n\) 均在 \(u\) 中出现
- 所有 \(\{u_i,t_i\}\) 两两不同
其中 \((u_i,t_i)\) 和 \((u_{i+1},t_{i+1})\) 的关系有两种
- Nastya从一个城市走到另一个城市,满足 \(u_i,u_{i+1}\) 之间有边相连, \(t_{i+1}=t_i+1\)
- Nastya使用了时间机器,满足 \(u_i=u_{i+1}\) , \(0 \le t_{i+1} < t_i\)
求一种使得 \(\max \{ t_1,t_2,\cdots,t_k \}\) 最小的方案.
Tutorial
考虑答案的下界为 \(T = \max \{\deg_i \}\) ,考虑构造.
我们想要找到一种方案使得到达一个节点 \(u\) 时,设当前时间为 \(t\) .每次找到一个未访问的儿子 \(v\) ,访问子树 \(v\) ,且满足从子树 \(v\) 回来时,时间为 \(t+1\) .分情况讨论
- 设 \(k=\deg_v-1\) ,如果 \(t+k+1 \le T\) ,那么就可以形如 \((u,t),(v,t+1),(w_1,t+2),\cdots,(v,t+k+1),(v,t),(u,t+1)\)
- 否则,可以形如 \((u,t),(v,t+1),(w_1,t+2),\cdots,(w_{T-t-1},T-1),(v,T),(v,t-(k-(T-t-1))),\cdots,(v,t),(u,t+1)\)
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std;
inline char nc()
{
// return getchar();
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
x=0; int f=1,ch=nc();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=nc();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10-‘0‘+ch;ch=nc();}
x*=f;
}
typedef pair<int,int> pii;
const int maxn=1e5+50;
int n;
int T;
int deg[maxn];
int head[maxn];
vector<int> adj[maxn];
vector<pii> an;
struct edge
{
int to,nex;
edge(int to=0,int nex=0):to(to),nex(nex){}
};
vector<edge> G;
inline void addedge(int u,int v)
{
G.push_back(edge(v,head[u])),head[u]=G.size()-1;
G.push_back(edge(u,head[v])),head[v]=G.size()-1;
++deg[u],++deg[v];
}
void dfs(int u,int t,int fa)
{
an.push_back(make_pair(u,t));
for(int i=head[u];~i;i=G[i].nex)
{
int v=G[i].to; if(v==fa) continue;
adj[u].push_back(v);
}
int k=adj[u].size();
int now=t;
for(int i=1;i<=k;++i)
{
int v=adj[u][i-1];
if(now==T)
{
now=t-1-(k-i+1);
an.push_back(make_pair(u,now));
}
dfs(v,now+1,u);
an.push_back(make_pair(u,++now));
}
if(u!=1&&now!=t-1) an.push_back(make_pair(u,t-1));
}
int main()
{
read(n);
memset(head,-1,sizeof(head));
for(int i=1;i<n;++i)
{
int u,v; read(u),read(v);
addedge(u,v);
}
T=*max_element(deg+1,deg+n+1);
dfs(1,0,0);
printf("%d\n",(int)an.size());
for(int i=0;i<an.size();++i)
{
printf("%d %d\n",an[i].fi,an[i].se);
}
return 0;
}