首页 > 代码库 > Codeforces Round #364 (Div. 1) 700B(树)
Codeforces Round #364 (Div. 1) 700B(树)
题目大意
在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; }
Codeforces Round #364 (Div. 1) 700B(树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。