标签：int root 贡献 100005 父亲 种树 配对
- 当然可以用树形DP做，但是转移的细节很多，关键是要将所有可能的情况纳入DP的设计中
- 四种情况：贡献1个给父亲、不需要父亲贡献、父亲贡献1个给该子树、父亲贡献2个给该子树
- 题解的做法：对于1个大小为n的、只有根节点完成的子树，需要的次数一定为n/2
- 另一种可能的做法：
- 方案自动机：我们只要安排一种非关键点间的配对关系，总存在一个合法的构造方案能将其全部变为关键点，因而我们可以忽略具体的操作过程（操作不一定和配对对应）
- 自底向上贪心，优先和兄弟配对，其次和父亲配对，其次和祖父配对
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005];
bool v[100005];
int sz[100005];
int n,m,ans,root;
void dp(int n1,int fa)
{
sz[n1]=1;
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
int y=a[n1][i];
dp(y,n1);
sz[n1]+=sz[y];
}
}
if(v[n1])
{
ans=ans+sz[n1]/2;
if(sz[n1]%2==0)
{
v[fa]=true;
}
sz[n1]=0;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
a[i].clear();
v[i]=false;
}
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
v[x]=true;
root=x;
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
ans=0;
dp(root,0);
cout<<ans<<"\n";
}
return 0;
}
标签：int,
root,
贡献,
100005,
父亲,
种树,
配对
From： https://www.cnblogs.com/watersail/p/18413589