【搜索】codeforces C. The Tag Game

http://codeforces.com/contest/813/problem/C

【题意】

给定一棵有n个结点的树，初始时Alice在根结点1,Bob在非根结点x;

Alice和Bob轮流走，每一步都有两种选择：走向相邻结点或静止不动，Bob先走；

当Alice和Bob相遇时游戏结束；

Alice的目标是游戏结束是的总步数最少，Bob的目标是游戏结束时总步数最少；

求最后的总步数是多少。

2 ≤ n ≤ 2·10^5， 2 ≤ x ≤ n

【思路】

Alice想要游戏尽早结束，所以Alice的每一步是靠近Bob; Bob不想游戏结束，所以他选择躲Alice,在尽量不遇到Alice的情况下选择一条最长的路径然后逃到这条路的叶节点不动。所以可以这样做：

bfs求出树上每个点k到1的距离dis[k]，O(n)
bfs求出树上每个点k到x的距离dist[k]，O(n)

如果dis[k]<dist[k]，说明k是可行点，在所有可行点中找到最大的dist[k]。

还有一种方法更复杂一点：

找出x到1的路径上的可行点k，所谓可行点就是当Bob到达这点的时候Alice还没有到达，1->k的路径长度+以结点K为根的子树高度

dfs一次找出每个点的深度和高度，O(n)

dfs一次找出1->x路径上的结点，O(n)

【Accepted】

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <cmath>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <set>
  7 #include <map>
  8 #include <queue>
  9 #include <deque>
 10 #include <stack>
 11 #include <string>
 12 #include <bitset>
 13 #include <ctime>
 14 #include<algorithm>
 15 #include<cstring>
 16 using namespace std;
 17 typedef long long ll;
 18 const int maxn=2e5+3;
 19 const int inf=0x3f3f3f3f;
 20 int n,x; 
 21 struct node
 22 {
 23     int to;
 24     int nxt;
 25 }edge[maxn<<1];
 26 int tot;
 27 int ans;
 28 int head[maxn];
 29 int du[maxn];
 30 int dis[maxn];
 31 int dist[maxn];
 32 void Init()
 33 {
 34     memset(head,-1,sizeof(head));
 35     memset(dis,inf,sizeof(dis));
 36     memset(dist,inf,sizeof(dist));
 37     tot=0;
 38     ans=0;
 39 }
 40 void add(int u,int v)
 41 {
 42     edge[tot].to=v;
 43     edge[tot].nxt=head[u];
 44     head[u]=tot++;
 45 }
 46 void bfs1(int u)
 47 {
 48     int vis[maxn];
 49     memset(vis,0,sizeof(vis));
 50     dist[u]=0;
 51     vis[u]=1;
 52     queue<int> Q;
 53     Q.push(u);
 54     while(!Q.empty())
 55     {
 56         u=Q.front();
 57         Q.pop();
 58         for(int i=head[u];i!=-1;i=edge[i].nxt)
 59         {
 60             int to=edge[i].to;
 61             if(vis[to])
 62             {
 63                 continue;
 64             }
 65             dist[to]=dist[u]+1;
 66             vis[to]=1;
 67             Q.push(to);
 68         }
 69     }
 70 }
 71 
 72 void bfs2(int u)
 73 {
 74     int vis[maxn];
 75     memset(vis,0,sizeof(vis));
 76     dis[u]=0;
 77     vis[u]=1;
 78     queue<int> Q;
 79     Q.push(u);
 80     while(!Q.empty())
 81     {
 82         u=Q.front();
 83         Q.pop();
 84         for(int i=head[u];i!=-1;i=edge[i].nxt)
 85         {
 86             int to=edge[i].to;
 87             if(vis[to])
 88             {
 89                 continue;
 90             }
 91             dis[to]=dis[u]+1;
 92             vis[to]=1;
 93             Q.push(to);
 94         }
 95     }
 96 }
 97 
 98 void Solve()
 99 {
100     bfs1(1);
101     bfs2(x);
102     for(int i=1;i<=n;i++)
103     {
104     //    cout<<dis[i]<<" "<<dist[i]<<endl;
105         if(dis[i]<dist[i])
106         {
107             ans=max(ans,dist[i]);    
108         }    
109     }
110     cout<<ans*2<<endl;
111 }
112 int main()
113 {
114     while(~scanf("%d%d",&n,&x))
115     {
116         Init();
117         int u,v;
118         for(int i=0;i<n-1;i++)
119         {
120             scanf("%d%d",&u,&v);
121             add(u,v);
122             add(v,u);
123             du[u]++;
124             du[v]++;
125         }
126         Solve();
127     }
128     return 0;
129 }

BFS

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <cmath>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <set>
  7 #include <map>
  8 #include <queue>
  9 #include <deque>
 10 #include <stack>
 11 #include <string>
 12 #include <bitset>
 13 #include <ctime>
 14 #include<algorithm>
 15 #include<cstring>
 16 using namespace std;
 17 typedef long long ll;
 18 
 19 int n,x;
 20 const int maxn=2e5+3;
 21 struct node
 22 {
 23     int to;
 24     int nxt;
 25 }edge[maxn<<1];
 26 int tot;
 27 int head[maxn];
 28 int du[maxn];
 29 int dep[maxn];
 30 int path[maxn];
 31 int vis[maxn];
 32 int d[maxn];
 33 int col;
 34 int ans;
 35 void Init()
 36 {
 37     memset(path,0,sizeof(path));
 38     memset(du,0,sizeof(du));
 39     memset(head,-1,sizeof(head));
 40     memset(dep,0,sizeof(dep));
 41     memset(vis,0,sizeof(vis));
 42     memset(d,0,sizeof(d));
 43     tot=0;
 44     col=0;
 45     ans=0;
 46 }
 47 void add(int u,int v)
 48 {
 49     edge[tot].to=v;
 50     edge[tot].nxt=head[u];
 51     head[u]=tot++;
 52 }
 53 
 54 int dfs(int u,int pre)
 55 {
 56     for(int i=head[u];i!=-1;i=edge[i].nxt)
 57     {
 58         int to=edge[i].to;
 59         if(to==pre)
 60         {
 61             continue;
 62         }
 63         dep[to]=dep[u]+1;
 64         d[u]=max(d[u],dfs(to,u)+1);
 65     }
 66     return d[u];
 67 }
 68 
 69 void pdfs(int u,int pre,int cnt)
 70 {
 71     if(col!=0)
 72     {
 73         return;
 74     }
 75     path[cnt]=u;
 76     if(u==x)
 77     {
 78         col=cnt;
 79         return;
 80     }
 81     for(int i=head[u];i!=-1;i=edge[i].nxt)
 82     {
 83         int to=edge[i].to;
 84         if(to==pre)
 85         {
 86             continue;
 87         }
 88         pdfs(to,u,cnt+1);
 89     }
 90 }
 91 void Solve()
 92 {
 93     dfs(1,0);
 94     pdfs(1,0,1);
 95     vis[1]=1;
 96     for(int i=col,k=2;i>=1,k<=col;i--,k++)
 97     {
 98         if(!vis[i])
 99         {
100             ans=max(ans,d[path[i]]+dep[path[i]]);
101         }
102         vis[k]=1;
103     }
104     cout<<ans*2<<endl;
105     
106 }
107 int main()
108 {
109     while(~scanf("%d%d",&n,&x))
110     {
111         Init();
112         int u,v;
113         for(int i=0;i<n-1;i++)
114         {
115             scanf("%d%d",&u,&v);
116             add(u,v);
117             add(v,u);
118             du[u]++;
119             du[v]++;
120         }
121         Solve();
122     }
123     return 0;
124 }

DFS