首先只要得到 \(x=0\) 时的答案，就可以 \(AC\) 本题。这是很重要的。
考虑由于不能有重复经过的边，所以两路径交点数量 \(\le 1\)。
容易想到设 \(dp_u\) 表示以 \(u\) 为端点的链中的贡献最大值。考虑换根 \(dp\)，所以先设它只表示它子树内的部分。
当交点数量 \(=1\) 时，显然可以理解为从一个节点出发的 \(0-4\) 条链，要这些链产生的贡献最大，所以要维护每个点的前四大链，这里的大指 \(dp\) 值大。
当交点数量 \(=0\) 时，可以看作是子树内有一条链，子树外有一条链的情况。
那么首先必须要维护前四大链 \(mx_{x,0/1/2/3}\)。
其次由于删掉一个点会产生儿子 \(+1\) 那么多个联通块，所以还要维护儿子数量 \(cnt_i\)。
考虑到子树内有一条链也得维护，所以得维护 \(f_i\) 表示过子树根的路径最大贡献，\(g_i\) 表示不一定过子树根的路径最大贡献。
由于 \(g_i\) 不好维护，所以再设 \(d_i\) 表示我们认为删掉 \(i\) 后 \(i\) 外还有联通块时，路径的最大贡献。那么就有：
\[\begin{cases} dp_x=cnt_i+\max(0,mx_{x,0}-1)\\ f_x=\max(dp_x,mx_{x,0}+mx_{x,1}+cnt_x-2)\\ g_x=\max(\max\limits_{y\in sn_x}d_y,f_x)\\ d_x=\max(\max\limits_{y\in sn_x}d_y,f_x+1) \end{cases} \]\(\max\limits_{y\in sn_x}d_y\) 可以通过预处理得到。换根时式子相同，所有定义中“子树内”全部改为“以该点为根的树”即可。
时间复杂度 \(O(tn)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,ans,mx[N][5],fmx[N][3];
int t,id,f[N],dp[N],g[N],d[N];
vector<int>ve[N];
void add(int x,int v){
mx[x][4]=v;
for(int i=3;~i;i--)
if(mx[x][i+1]>mx[x][i])
swap(mx[x][i+1],mx[x][i]);
}void adf(int x,int v){
fmx[x][2]=v;
for(int i=1;~i;i--)
if(fmx[x][i+1]>fmx[x][i])
swap(fmx[x][i+1],fmx[x][i]);
}void dfs1(int x,int fa){
int cnt=ve[x].size()-1;
for(auto y:ve[x]) if(y!=fa)
dfs1(y,x),add(x,dp[y]),adf(x,d[y]);
dp[x]=cnt+max(1,mx[x][0])-1;
f[x]=max(dp[x],mx[x][0]+mx[x][1]+cnt-2);
g[x]=max(fmx[x][0],f[x]);
d[x]=max(fmx[x][0],f[x]+1);
}void dfs2(int x,int fa){
int sz=ve[x].size(),cnt=sz-1;
for(int i=0;i<5;i++)
ans=max(ans,sz),sz+=mx[x][i]-1;
for(auto y:ve[x]){
if(y==fa) continue;
int mo=mx[x][0]+mx[x][1];
int mz=mx[x][0],mt=fmx[x][0];
if(dp[y]==mx[x][0])
mo+=mx[x][2]-mz,mz=mx[x][1];
if(dp[y]==mx[x][1]) mo=mz+mx[x][2];
if(fmx[x][0]==d[y]) mt=fmx[x][1];
dp[x]=cnt+max(1,mz)-1;
f[x]=max(dp[x],mo+cnt-2),add(y,dp[x]);
g[x]=max(mt,f[x]),d[x]=max(mt,f[x]+1);
adf(y,d[x]),ans=max(ans,g[x]+f[y]),dfs2(y,x);
}
}void solve(){
for(int i=1;i<=n;i++){
ve[i].clear(),g[i]=d[i]=f[i]=dp[i]=0;
mx[i][0]=mx[i][1]=mx[i][2]=mx[i][3]=0;
fmx[i][0]=fmx[i][1]=0;
}cin>>n;int tmp;
for(int i=0;i<id*2;i++) cin>>tmp;
for(int i=1,x,y;i<n;i++)
cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
ans=0,dfs1(1,0),dfs2(1,0),cout<<ans<<"\n";
}int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t>>id;
while(t--) solve();
return 0;
}