【题解】直径之差

题意

给你两棵二叉树和，从和中各选一个节点，并在他们之间添加一条边得到新树，问可能的最长直径和最短直径之差是多少。

题解

首先我们分别求出树和树的直径。首先新树的最长直径怎么连接可以得到呢，我们只用将树和树直径两端各选一个节点相连，那么的直径就是。那么最短直径呢，我们可以取树直径中点和树直径的中点在他们之间连接一条边，即，那么我们就可以得到两者之差了，。如何求一棵树的直径我们做两遍，首先随意取一个点出发，从其达到的最远点就肯定是直径的一端了，我们在以该端为起点再做一次到达最远点的路径就是直径了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>E[N];
int vis[N];
int d=0;
int p;
void dfs(int u,int h)
{
    vis[u]=1;
    if(h>d)
    {
        d=h;
        p=u;
    }
    for(int i=0;i<E[u].size();i++)
    {
        int v=E[u][i];
        if(!vis[v])
        {
            dfs(v,h+1);
        }
    }
}
int main()
{
    int n;
    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);
    }
    dfs(1,0);
    memset(vis,0,sizeof(vis));
    d=0;
    dfs(p,0);
    int d1=d;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        E[i].clear();
    memset(vis,0,sizeof(vis));
    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);
    }
    d=0;
    dfs(1,0);
    memset(vis,0,sizeof(vis));
    d=0;
    dfs(p,0);
    int d2=d;
    printf("%d\n",d1+d2-(d1+1)/2-(d2+1)/2);
    return 0;
}