思路很简单，子树不同分支↵
没学lca，但是这题有明确主干，就是直接找公共祖先在主干上的点而且不是1↵
没有必要连上再减去一部分，直接全局算距离↵
树一般默认无向，无语，因为这个一直错↵
！！！没必要思考怎么连这个树，加边减边很难做，直接全局变量考虑↵
↵
~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int N=5e5+10;↵
vector<int>g[N];↵
int par[N],dep[N];↵
bool ok[N];↵
int f[N];↵
void dfs1(int u,int p,int d)↵
{↵
par[u]=p;↵
dep[u]=d;↵
for(int v:g[u])↵
{↵
if(v!=p)↵
{↵
dfs1(v,u,d+1);↵
}↵
}↵
}↵
void dfs2(int u,int p)↵
{↵
if(u!=1)↵
{↵
f[u]=ok[u]?u:f[p];↵
}↵
for(int v:g[u])↵
{↵
if(v!=p)↵
{↵
dfs2(v,u);↵
}↵
}↵
}↵
void solve()↵
{↵
int n,m;cin>>n>>m;↵
for(int i=1;i<=n;i++)↵
{↵
g[i].clear();↵
par[i]=0;dep[i]=0;↵
ok[i]=false;f[i]=0;↵
}↵
int t=n-1;↵
while(t--)↵
{↵
int a,b;cin>>a>>b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
dfs1(1,0,0);↵
for(int i=n;i!=0;i=par[i])↵
{↵
ok[i]=true;↵
}↵
f[1]=1;↵
dfs2(1,0);↵
int ans=dep[n];↵
while(m--)↵
{↵
int x;cin>>x;↵
if(!ok[x]&&f[x]!=1)↵
{↵
ans=max(ans,dep[x]+dep[n]-dep[f[x]]*2+1);↵
}↵
}↵
cout<<ans<<'\n';↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~
没学lca，但是这题有明确主干，就是直接找公共祖先在主干上的点而且不是1↵
没有必要连上再减去一部分，直接全局算距离↵
树一般默认无向，无语，因为这个一直错↵
！！！没必要思考怎么连这个树，加边减边很难做，直接全局变量考虑↵
↵
~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
const int N=5e5+10;↵
vector<int>g[N];↵
int par[N],dep[N];↵
bool ok[N];↵
int f[N];↵
void dfs1(int u,int p,int d)↵
{↵
par[u]=p;↵
dep[u]=d;↵
for(int v:g[u])↵
{↵
if(v!=p)↵
{↵
dfs1(v,u,d+1);↵
}↵
}↵
}↵
void dfs2(int u,int p)↵
{↵
if(u!=1)↵
{↵
f[u]=ok[u]?u:f[p];↵
}↵
for(int v:g[u])↵
{↵
if(v!=p)↵
{↵
dfs2(v,u);↵
}↵
}↵
}↵
void solve()↵
{↵
int n,m;cin>>n>>m;↵
for(int i=1;i<=n;i++)↵
{↵
g[i].clear();↵
par[i]=0;dep[i]=0;↵
ok[i]=false;f[i]=0;↵
}↵
int t=n-1;↵
while(t--)↵
{↵
int a,b;cin>>a>>b;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
dfs1(1,0,0);↵
for(int i=n;i!=0;i=par[i])↵
{↵
ok[i]=true;↵
}↵
f[1]=1;↵
dfs2(1,0);↵
int ans=dep[n];↵
while(m--)↵
{↵
int x;cin>>x;↵
if(!ok[x]&&f[x]!=1)↵
{↵
ans=max(ans,dep[x]+dep[n]-dep[f[x]]*2+1);↵
}↵
}↵
cout<<ans<<'\n';↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int t;cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~
