hdu 4607 Park Visit dfs

简介:

   这题题意很好理解,就是要找到个最大长度,比赛的时候就在纠结怎么找,一开始想dfs怕超时,后来用并查集乱搞过了,看了标程果然是dfs,但只要2次就可以了,显然。

   于是自己又敲了一遍


/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
vector<int>node[100005];
int d[100005];
void dfs(int u,int f,int dp)
{
    d[u]=dp;
    for(int i=0;i<node[u].size();i++)
        if(node[u][i]!=f)dfs(node[u][i],u,dp+1);
}
int main()
{
    int T,n,m,k,K,i,v,u;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)node[i].clear();
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&v,&u);
            node[u].push_back(v);
            node[v].push_back(u);
        }
        K=1;
        dfs(K,0,1);
        for(i=1;i<=n;i++) if(d[i]>d[K])K=i;//直径的一个端点
        dfs(K,0,1);
        for(i=1;i<=n;i++) if(d[i]>d[K])K=i;//另一个端点
        K=d[K];
        while(m--)
        {
            scanf("%d",&k);
            if(k<=K)printf("%d\n",k-1);
            else printf("%d\n",K-1+2*(k-K));
        }
    }
}



目录
相关文章
|
7月前
|
流计算
POJ 3620--Avoid The Lakes【DFS】
POJ 3620--Avoid The Lakes【DFS】
36 0
|
Java
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
hdu1016 Prime Ring Problem【素数环问题(经典dfs)】
62 0
Find The Multiple(dfs和bfs都可)
Find The Multiple(dfs和bfs都可)
28 0
codeforces1244——D.Paint the Tree(dfs)
codeforces1244——D.Paint the Tree(dfs)
87 0
CF1454 E. Number of Simple Paths (基环树 拓扑排序)
CF1454 E. Number of Simple Paths (基环树 拓扑排序)
94 0
HDU-1016,Prime Ring Problem(DFS+素数)
HDU-1016,Prime Ring Problem(DFS+素数)
|
机器人
HDU-1035,Robot Motion(DFS)
HDU-1035,Robot Motion(DFS)