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

Codeforces Round #199 (Div. 2) E. Xenia and Tree （非正规解法 分情况dfs）
E. Xenia and Treetime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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:

1. paint a specified blue node in red;
2. 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.

The first line contains two integers n and m (2?≤?n?≤?10^{5,?1?≤?m?≤?105) — 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,?bi (1?≤?ai,?bi?≤?n,?ai?≠?bi) — an edge of the tree.}}

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

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

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

5 41 22 32 44 52 12 51 22 5

032

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

思路：

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

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define maxn 100005#define INF 0x3f3f3f3fusing 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

离线算法。应该就这么做的嘛。

Re: u010228612昨天 23:43

回复y5885922n不是 这个方法本质上复杂度还是没降下来 很简单就可以出卡这个程序的数据