CodeForces - 748F Santa Clauses and a Soccer Championship（思路）

思路：由于整个结构为树，则每个点之间的最短路径唯一，则可以发现住宿处个数存在且最小为1。则住宿处为某一点将所有team分成两部分且在所有配对的team的最短路上，则住宿处的位置为某子树中包含家乡的点的个数不小于k的最小子树的根节点。则分队可以将该子树的两部分直接分配：dfs过程中将家乡加入左边部分，当左边部分个数等于k时，开始将点加入右边部分，最后将左边与右边的点输出即可（住宿处作为根节点将所有家乡分成两部分，所以住宿处必在所有点之间的最短路上，所以可以直接分配）。

#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>#define debuusing namespace std;const int maxn=2e5+50;int vis[maxn];int n,k,root,sum;int home[maxn];vector<int> one,two;vector<int> g[maxn];int find_Root(int u){    int sum=home[u]?1:0;    for(int i=0; i<g[u].size(); i++)    {        int nt=g[u][i];        if(!vis[nt])        {            vis[nt]=1;            sum+=find_Root(nt);        }    }    if(sum>=k&&root==-1) root=u;    return sum;}void solve(int u){    if(home[u])    {        if(one.size()<k) one.push_back(u);        else two.push_back(u);    }    for(int i=0; i<g[u].size(); i++)    {        int nt=g[u][i];        if(!vis[nt])        {            vis[nt]=1;            solve(nt);        }    }}int main(){#ifdef debug    freopen("in.in","r",stdin);#endif // debug    scanf("%d%d",&n,&k);    for(int i=0; i<n-1; i++)    {        int u,v;        scanf("%d%d",&u,&v);        g[u].push_back(v);        g[v].push_back(u);    }    for(int i=0; i<2*k; i++)    {        int x;        scanf("%d",&x);        home[x]=1;    }    memset(vis,0,sizeof(vis));    vis[1]=1,root=-1;    find_Root(1);    memset(vis,0,sizeof(vis));    vis[root]=1;    solve(root);    printf("1/n%d/n",root);    for(int i=0; i<one.size(); i++)        printf("%d %d %d/n",one[i],two[i],root);    return 0;}