Codeforces Round #199 (Div. 2) E. Xenia and Tree

题目链接

2了，差点就A了。。。这题真心不难，开始想的就是暴力spfa就可以，直接来了一次询问，就来一次的那种，TLE了，想了想，存到栈里会更快，交又TLE了。。无奈C又被cha了，我忙着看C去了。。。这题，是我一个地方写错了。。top = 0的时候会死循环吗？貌似不会把，反正我加了这个判断，就A了，可能优化了一下把。

 #include <cstring>

 #include <cstdio>

 #include <string>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <queue>

 using namespace std;

 #define INF 1000000

 int first[];

 int dis[];

 int in[];

 int s[];

 int n,t,top;

 struct node

 {

     int u,v,next;

 }edge[];

 void CL()

 {

     t = ;

     memset(first,-,sizeof(first));

 }

 void add(int u,int v)

 {

     edge[t].u = u;

     edge[t].v = v;

     edge[t].next = first[u];

     first[u] = t ++;

 }

 void spfa()

 {

     int i,u,v;

     for(i = ;i <= n;i ++)

     in[i] = ;

     queue<int>que;

     for(i = ;i < top;i ++)

     {

         in[s[i]] = ;

         dis[s[i]] = ;

         que.push(s[i]);

     }

     while(!que.empty())

     {

         u = que.front();

         que.pop();

         in[u] = ;

         for(i = first[u];i != -;i = edge[i].next)

         {

             v = edge[i].v;

             if(dis[v] > dis[u] + )

             {

                 dis[v] = dis[u] + ;

                 if(!in[v])

                 {

                     in[v] = ;

                     que.push(v);

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     int m,i,u,v;

     CL();

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

     for(i = ;i < n;i ++)

     {

         scanf("%d%d",&u,&v);

         add(u,v);

         add(v,u);

     }

     for(i = ;i <= n;i ++)

     dis[i] = INF;

     top = ;

     s[] = ;

     spfa();

     top = ;

     for(i = ;i <= m;i ++)

     {

         scanf("%d%d",&u,&v);

         if(u == )

         {

             s[top ++] = v;

         }

         else

         {

             if(top != )//这里

             spfa();

             top = ;

             printf("%d\n",dis[v]);

         }

     }

     return ;

 }