CF592D Super M

妈的还在做水题

这题乍一看感觉要建虚树，但后面一想建个屁又没有多次询问直接DFS一遍把子树里没有关键点的点全删了就完事了

然后第一直觉是来个树上DP啥的，设两个状态表示子树内走了回来/不回来的最小代价

但后面冷静了一下仔细一想其实每条边都是要走两次的，除了起点到终点这条路径上的所有边可以只走一次

那么现在的问题就变成找直径了，直接两遍DFS解决即可，注意长度相同时保留编号最小的端点

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=125000;
int n,m,x,y,key[N],mx,pos,tot,ans; vector <int> v[N];
inline void DFS1(CI now,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa) DFS1(to,now),key[now]|=key[to]; tot+=key[now];
}
inline void DFS2(int now,CI fa=0,CI d=0)
{
	if (!key[now]) return;
	if (d>mx||(d==mx&&now<pos)) mx=d,pos=now;
	for (auto to:v[now]) if (to!=fa) DFS2(to,now,d+1);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (i=1;i<=m;++i) scanf("%d",&x),key[x]=1;
	if (m==1) return printf("%d\n0",x),0;
	DFS1(x); mx=-1; DFS2(x); ans=pos; mx=-1; DFS2(pos);
	return printf("%d\n%d",min(ans,pos),2*(tot-1)-mx),0;
}