题目大意
在n颗结点的树上有2k个需要配对的点,把他们两两配对,使得路程和最大并输出
选取一个点v
lv表示v与父亲的边
那么考虑lv被经过的次数,对于一个最大的情况,lv应该为min(sv, 2*k - sv) ,其中sv是v子树中需要配对的点(包括v)
假如lv比这个值小,那么必定有a和b在v的子树外,c和d在子树内,它们分别配对
但是如果这样的话,让a和c配对,b和d配对,显然更优
所以lv只能等于min(sv, 2*k - sv)
最后输出所有点的这个值的和即可
#include <iostream> #include <cstdio> #include <vector> using namespace std; long long sz[222222], ans; vector <int> G[222222]; void dfs(int x, int fa) { for(int i = 0; i < G[x].size(); i++) { int to = G[x][i]; if(to == fa) continue; dfs(to, x); sz[x] += sz[to]; } } int n, k, x, y; int main() { cin>>n>>k; for(int i = 1; i <= 2*k; i++) cin>>x, sz[x]++; for(int i = 1; i < n; i++) { cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } dfs(1, 1); for(int i = 2; i <= n; i++) ans += min(sz[i], 2*k - sz[i]); cout<<ans<<endl; }