NC223205. B 天平
描述
输入描述
第一行，n，m。
第二行，m 个数，表示每种物品的质量。
接下来若干行，每行三个数 u，x，y。表示在 u 物品下的两个物品编号分别为 x，y。行数是可以推知的。
保证整个树形结构的根是 1。
输出描述
一行，表示最终的答案。
示例1
输入:
3 3 2 3 4 1 2 3
输出:
2
示例2
输入:
7 3 1 3 4 1 2 3 3 4 5 4 6 7
输出:
8
C++ 解法, 执行用时: 379ms, 内存消耗: 25572K, 提交时间: 2021-09-17 19:17:12
#include<bits/stdc++.h>
#define N 55
#define M 2505
#define pb push_back
using namespace std;
int n,m,w[N],f1[M][M],tmp[M],siz[M],f[N][M],ans=2e9;
vector<int>adj[N];
void cmin(int &x,int y){x=x<y?x:y;}
void dfs(int x){
siz[x]=1;
if(!adj[x].empty()){
int X=adj[x][0],Y=adj[x][1];
dfs(X),dfs(Y),siz[x]+=siz[X],siz[x]+=siz[Y];
memset(tmp,0x3f,sizeof(tmp));
for(int i=1;i<=siz[X]*50;i++)
for(int j=1;j<=siz[Y]*50;j++)cmin(tmp[i+j],f[X][i]+f[Y][j]+(i+j)/f1[i][j]);
}else{
memset(tmp,0x3f,sizeof(tmp));
tmp[0]=0;
}
for(int i=1;i<=m;i++)for(int j=0;j<=siz[x]*50;j++)cmin(f[x][j+w[i]],tmp[j]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>w[i];
for(int i=1,u,x,y;i*2<=n;i++)cin>>u>>x>>y,adj[u].pb(x),adj[u].pb(y);
for(int i=1;i<M;i++)for(int j=1;j<M;j++)f1[i][j]=__gcd(i,j);
memset(f,0x3f,sizeof(f)),dfs(1);
for(int i=0;i<M;i++)cmin(ans,f[1][i]);
cout<<ans<<'\n';
return 0;
}