Codeforces Round #199 (Div. 二) E. Xenia and Tree （非正规解法分情况dfs）

Codeforces Round #199 (Div. 2) E. Xenia and Tree （非正规解法分情况dfs）

Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.

The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.

Xenia needs to learn how to quickly execute queries of two types:

paint a specified blue node in red;
calculate which red node is the closest to the given one and print the shortest distance to the closest red node.

Your task is to write a program which will execute the described queries.

Input

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵) — the number of nodes in the tree and the number of queries. Next n - 1 lines contain the tree edges, the i-th line contains a pair of integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — an edge of the tree.

Next m lines contain queries. Each query is specified as a pair of integers t_i, v_i (1 ≤ t_i ≤ 2, 1 ≤ v_i ≤ n). If t_i = 1, then as a reply to the query we need to paint a blue node v_i in red. If t_i = 2, then we should reply to the query by printing the shortest distance from some red node to node v_i.

It is guaranteed that the given graph is a tree and that all queries are correct.

Output

For each second type query print the reply in a single line.

Sample test(s)

input
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5

output
0
3
2

ps：我的做法是非正规解法，数据水了，就过了。正规解法不会，网上也找不到，以后会了再贴。

思路：

分情况讨论，如果操作1多的话，就对2进行搜索，输出答案。如果操作2多的话，就对1进行搜索，用dp[ ]保存，遇到2直接输出。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005
#define INF 0x3f3f3f3f
using namespace std;

int n,m,ans,cnt,cnt1,cnt2;
bool vis[maxn];
int pp[maxn],c[maxn],dp[maxn];
int x[maxn],y[maxn];
struct Node
{
    int v,next;
}edge[2*maxn];

void addedge(int u,int v)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].next=pp[u];
    pp[u]=cnt;
}
void dfs(int u,int step)   //针对操作１多的情况
{
    if(step>=ans) return ;
    if(c[u])
    {
        if(ans>step) ans=step;
        return ;
    }
    int i,j,v;
    for(i=pp[u];i;i=edge[i].next)
    {
        v=edge[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v,step+1);
        }
    }
}
void dfs1(int u,int step)　　//针对操作２多的情况
{
    if(dp[u]<=step) return ;
    dp[u]=step;
    int i,j,v;
    for(i=pp[u];i;i=edge[i].next)
    {
        v=edge[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            dfs1(v,step+1);
        }
    }
}
void solve()
{
    int i,j;
    if(cnt1>cnt2)
    {
        c[1]=1;
        for(i=1;i<=m;i++)
        {
            if(x[i]==1) c[y[i]]=1;
            else
            {
                ans=INF;
                memset(vis,0,sizeof(vis));
                vis[y[i]]=1;
                dfs(y[i],0);
                printf("%d\n",ans);
            }
        }
    }
    else
    {
        memset(dp,0x3f,sizeof(dp));
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs1(1,0);
        for(i=1;i<=m;i++)
        {
            if(x[i]==1)
            {
                memset(vis,0,sizeof(vis));
                vis[y[i]]=1;
                dfs1(y[i],0);
            }
            else printf("%d\n",dp[y[i]]);
        }
    }
}
int main()
{
    int i,j,u,v;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(pp,0,sizeof(pp));
        memset(c,0,sizeof(c));
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        cnt1=cnt2=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            if(x[i]==1) cnt1++;
            else cnt2++;
        }
        solve();
    }
    return 0;
}

1楼y5885922昨天 23:17: 离线算法。应该就这么做的嘛。

Codeforces Round #199 (Div. 二) E. Xenia and Tree （非正规解法 分情况dfs）

相关推荐

Codeforces Round #199 (Div. 二) E. Xenia and Tree （非正规解法分情况dfs）