題目鏈接：點擊查看

題目大意：給出一棵樹，現在要求從點1出發遍歷所有的結點一遍后再回到點1，額外給出一個時光機，可以到某個節點的任意時刻，需要滿足的條件如下：

初始時在節點 1 ，時間為 0?

每次操作分為下列兩種：

( v , t ) -> ( v , t_pre ) ，滿足 0 <= t_pre < t （利用時光機）

( v , t ) -> ( v_next , t + 1 ) ，滿足 v 和 v_next 之間存在一條連邊 （正常行走）

所有的 ( v , t ) 必須各不相同

所有的節點必須至少被遍歷一遍

在上述條件下，若要使得所有 t 中的最大值最小，輸出一種構造方案

題目分析：其實不難看出，最終所有 t 中的最大值，和每個點的度數有關系，所以我們可以求出這個最大值為 mmax ，也就是最大的時間點，接下來需要想出一種構造方案，使得既能滿足利用時光機時不能沖突，也要滿足正常行走的條件，這里直接給出構造方法吧

首先對于任意一個節點 u 來說，先求出他的所有子節點有多少個，記為 son ，不難看出，節點 u 至少需要經過 son + 1 次才行，一次是從節點 u 的父節點下來，剩下 son 次是從子節點上來，同時可以知道， 0 <= son < mmax ，當節點為葉子結點時，son 顯然為 0 ，當節點為度數最大的那個節點時，son = mmax - 1 （減去父節點）

到此為止，我們先考慮滿足每個操作的第二種情況，也就是正常行走的情況，這種情況必須要求從節點 u 到達節點 v 時，時間之差必須為一，如果我們先不考慮最大值 mmax 的限制的話，設從父節點到節點 u 的時間點為 t 的話，我們可以讓節點 u 到子節點的時間分別為 t + 1? , t + 2 , t + 3 .... 以此類推，如何保證呢？只需要根據相對關系實現下面兩點即可：（設 t_u 為進入到節點 u 時的時間，t_v 為進入到子節點 v 時的時間）

從節點 u 進入到子節點時的時間為 t_u + 1

從子節點返回到到節點 u 時的時間為 t_v - 1

仔細思考一下，會發現確實很巧妙

那么剩下的就是解決有 mmax 限制的那個時光機的條件了，因為每個節點的每個時間點至多只能出現一次，而每個節點最多就會使用 son + 2 次時間點：

一次是從父節點下來時的 t

son 次是從子節點上來時的 t + 1 , t + 2 ...等等

一次是從最大值轉到最小值時使用的（多使用了一次時光機）

所以我們可以將每個結點使用的區間固定在 [ mmax - son - 1 , mmax ] 之間，換句話說，就是讓節點 u 到子節點的時間分別為 t + 1 , t + 2 , t + 3 .... ( mmax - son - 1 ) +1 , ( mmax - son - 1 ) + 2 .... t - 1 ，也就是當 t 到達 mmax 時，讓其變為最小值?mmax - son - 1 然后繼續加一就行了

注意特判一下節點 1

利用 dfs 實現起來非常簡單，終點是需要理解構造的巧妙

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>node[N];vector<pair<int,int>>ans;int mmax;void dfs(int u,int fa,int t)//在區間 [ mmax - son - 1 , mmax ] 內賦值 {int temp=t;ans.push_back(make_pair(u,t));int son=node[u].size()-(u!=1);//有多少個子節點 for(auto v:node[u]){if(v==fa)continue;if(t==mmax)//如果已經到最大值了，那么切換成最小值 {t=mmax-son-1;ans.push_back(make_pair(u,t));}t++;dfs(v,u,t);ans.push_back(make_pair(u,t));}if(u!=1&&t!=temp-1)ans.push_back(make_pair(u,temp-1)); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}for(int i=1;i<=n;i++)mmax=max(mmax,(int)node[i].size());dfs(1,-1,0);printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1341F Nastya and Time Machine(dfs+构造)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。