题解：P3023 [USACO11OPEN] Soldering G
tom_l
·
·
题解
提供一篇目前没被 hack 的题解
考虑 O(n^2) 的做法
有 $2$ 种转移，如图，红色和黑色表示将黑色线接在红色线的中间位置。
设当前节点为 $x$，儿子为 $y$。
1. 选一个儿子节点，将其他儿子节点连在其上，计算其他儿子的贡献。
先对每个儿子节点统计最小贡献：
$$mn_y \gets \min\{f_{y,j}+(j+1)^2\}$$
再计算总的贡献：
$$res\gets\sum _ {y\in son{x}} mn_y$$
最后进行转移：
$$f_{x,j}\gets\min\{f_{y,j-1}+res-mn_y,f_{x,j}\}$$
3. 选两个儿子节点连在一起，计算所有的贡献。
枚举儿子 $i$ 和 $j$，有转移：
$$f_{x,0}\gets \min \{ f_{x,0},f_{i,s1}+f_{j,s2}+(s1+s2+2)^2+res-mn_i-mn_j \}$$
#### 考虑优化
去掉多余的状态。
对于 $f_{x,i}$ 和 $f_{x,j}$，当 $i>j$ 且 $f_{x,i}+i^2 \ge f_{y,j}+j^2$ 时，显然 $f_{x,i}$ 无意义，可以删去，最后用 `vector` 存 $f_{x}$ 即可通过此题。此时已经可以通过官方数据了，但会被菊花图卡。瓶颈在于第二种转移，发现对于儿子节点超过两个的相同状态对此转移无意义，用 `map` 去重。
#### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n;
vector<pair<int,int> >f[N];
int mn[N];
void work(vector<pair<int,int> >&p){
sort(p.begin(),p.end());
vector<pair<int,int> >tmp;
for(auto i:p){
if(tmp.empty()||i.second+i.first*i.first<tmp.back().second+tmp.back().first*tmp.back().first)tmp.push_back(i);
}
p=tmp;
}
vector<int>e[N];
struct node{
int first,second,id;
};
void dfs(int x,int fa){
for(int y:e[x]){
if(y==fa)continue;
dfs(y,x);
}
int res=0;
for(int y:e[x]){
if(y==fa)continue;
mn[y]=1e18;
for(auto i:f[y]){
int l=i.first,s=i.second;
l++;
mn[y]=min(s+l*l,mn[y]);
}
res+=mn[y];
}
for(int y:e[x]){
if(y==fa)continue;
for(auto i:f[y]){
int l=i.first,s=i.second;
f[x].emplace_back(l+1,res-mn[y]+i.second);
}
}
int ad=1e18;
map<int,map<unsigned long long ,map<long long,int> > >mp;
vector<node >tmp;
for(int y:e[x]){
for(auto i:f[y]){
mp[i.first][i.second][mn[y]]++;
if(mp[i.first][i.second][mn[y]]<=2)tmp.push_back({i.first,i.second,y});
}
}
for(auto i:tmp){
for(auto j:tmp){
if(i.id==j.id)continue;
int tres=res-mn[i.id]-mn[j.id];
ad=min(ad,tres+i.second+j.second+(i.first+j.first+2)*(i.first+j.first+2));
}
}
f[x].emplace_back(0 , ad );
if(e[x].size()==1){
if(e[x][0]==fa){
f[x].emplace_back(0,0);
}
else {
for(auto i:f[e[x][0]]){
f[x].emplace_back(0,i.second+(i.first+1)*(i.first+1));
}
}
}
for(int y:e[x]){
if(y!=fa){
f[y].clear();
f[y].shrink_to_fit();
}
}
work(f[x]);
}
signed main (){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1,0);
if(f[1].empty()){
cout<<"E";
//调试时防止程序崩溃
exit(0);
}
cout<<f[1][0].second;
return 0;
}
```