The 2018 ACM-ICPC CCPC 영하G-Factories(트리 dp+백팩)

제목: n개의 도시, n-1개의 도로를 드리겠습니다. 두 도시마다 하나의 통로, 즉 나무 구조가 있습니다.최종적으로 임의의 두 공장 사이의 거리를 누적하고 최소화하기 위해 m개의 잎 노드를 선택하여 공장을 세우라고 합니다.
사고방식: 고려점 간의 관계는 매우 번거롭기 때문에 나는 한 변에 대해 고려가 몇 번을 거쳤는지 생각한다.dp[u][i]는 u 노드가 뿌리인 자수에서 i개의 잎 노드를 선택하면 u라는 자수의 가장자리를 지나는 권한과 최우수값을 나타낸다.전환 방정식은 다음과 같습니다.
dp[u][i]=min( dp[u][i-j]+dp[v][j]+w*j*(m-j) ); v는 u의 서브노드이고 w는 u와 v 사이의 권한값이다. k*(m-k)는 이 변이 지나갈 횟수를 표시한다(j는 v라는 나무에서 오는 잎사귀 포인트이고 m-j는 다른 곳에서 선택한 잎사귀 포인트이다)
내가 왜 지적 장애자야? 생각이 벌써 맞았어. 아무리 생각해도 틀림없어. 계속wa를 했는데 마지막에 결과가'Case #%d:%lld'를 출력해야 한다는 걸 알았어!!!!바보 같은 실수를 계속 범하고freopen()도 주의해야 해!

#include 
using namespace std;
#define ll long long
#define inf 1e12
const int maxn=1e5+10;
struct node{
    int x;
    ll w;
    node(int _x,ll _w)
    {
        x=_x;
        w=_w;
    }
};
vectora[maxn];
int n,t,m,siz[maxn];
ll dp[maxn][102];
void dfs(int u,int fa)
{
    if(a[u].size()==1)
    {
        dp[u][1]=0;
        siz[u]=1;///       
    }
    dp[u][0]=0;
    for(int i=0;i=1;j--)
{
for(int k=1;k<=min(j,siz[v]);k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+1ll*w*1ll*k*1ll*(m-k));//전이 방정식
}
}
}
int main()
{
///freopen("in.txt","r",stdin);
scanf("%d",&t);
int cas=0;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
a[i].clear();
for(int i=1;i1)
{
rt=i;
break;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=inf;
for(int i=1;i<=n;i++)
dp[i][0]=0;
dfs(rt,-1);
printf("Case #%d: %lld",++cas,dp[rt][m]);
}
return 0;
}