[cf1340D]Nastya and Time Machine

记$deg_{i}$为$i$的度数，简单分类讨论可得答案下限为$\max_{i=1}^{n}deg_{i}$

另一方面，此下限是可以取到的，构造方法较多，这里给一个巧妙一些的做法——

对其以dfs（儿子顺序任意），并要求如果一个节点被父亲递归时时间为$t+1$，则返回时时间为$t$，那么父亲的时间即恰从$t$变为$t+1$

下面考虑如何保证此性质，每一个节点有两种情况：

1.其过程中某次要递归儿子时，其时间达到了$\max_{i=1}^{n}deg_{i}$（那么搜下去即超过了此下限），那么将其的时间改为$t-son$（其中$t+1$为其被父亲递归时时间，$son$为剩余儿子数，显然$t\ge son$）

2.某点不存在上述情况，则在最后将其的时间改为$t$（意义与上面相同）

由此，即可归纳上述性质

时间复杂度为$o(n)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 vector<int>v[N];

 5 vector<pair<int,int> >ans;

 6 int n,T,x,y,lim;

 7 void dfs(int k,int fa){

 8     int t=T-1;

 9     for(int i=0;i<v[k].size();i++)

10         if (v[k][i]!=fa){

11             if (T==lim){

12                 T=t;

13                 for(int j=i;j<v[k].size();j++)

14                     if (v[k][j]!=fa)T--;

15                 ans.push_back(make_pair(k,T));

16             }

17             ans.push_back(make_pair(v[k][i],++T));

18             dfs(v[k][i],k);

19             ans.push_back(make_pair(k,++T));

20         }

21     if ((k!=1)&&(t!=T)){

22         ans.push_back(make_pair(k,t));

23         T=t;

24     }

25 }

26 int main(){

27     scanf("%d",&n);

28     for(int i=1;i<n;i++){

29         scanf("%d%d",&x,&y);

30         v[x].push_back(y);

31         v[y].push_back(x);

32     }

33     for(int i=1;i<=n;i++)lim=max(lim,(int)v[i].size());

34     ans.push_back(make_pair(1,0));

35     dfs(1,0);

36     printf("%d\n",(int)ans.size());

37     for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);

38     return 0;

39 }

巴特西

[cf1340D]Nastya and Time Machine

最新文章

热门文章