可以直接普通dfs过掉,但是现有题解里好像没有这样的做法
查看原帖
可以直接普通dfs过掉,但是现有题解里好像没有这样的做法
29872
27号兔先生楼主2020/7/1 11:36
#include<bits/stdc++.h>
#define MX 200000
using namespace std;

int n, x, y, dep[MX], ans, cnt[MX];
vector<int> e[MX];

void dfs(int x, int fa)
{
    for(int i=0;i<e[x].size();i++)
    {
        int son = e[x][i];
        if(son == fa)
            continue;
        dep[son] = dep[x] + 1;
        dfs(son, x);
    }
}

void dfs1(int x, int w, int frm)
{
    if(x == y)
    {
        ans = w;
    }
    for(int i=0;i<e[x].size();i++)
    {
        int son = e[x][i];
        if(son == frm)
            continue;
        if(dep[son] > dep[x])
            dfs1(son, w + 1, x);
        else 
            dfs1(son, w + 2, x);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<n;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    scanf("%d%d", &x, &y);
    dep[1] = 1;
    dfs(1, 1);
    dfs1(x, 0, 0);
    int maxdep = 0;
    int maxwid = 0;
    for(int i=1;i<=n;i++)
    {
        maxdep = max(dep[i], maxdep);
        cnt[dep[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        maxwid = max(cnt[i], maxwid);
    }
    printf("%d\n%d\n%d", maxdep, maxwid, ans);
}
2020/7/1 11:36
加载中...