codeforces F - Maximum Weight Subset

좋은 문제지만 나는 할 줄 모른다.
나무의 최대 권한 값 집합을 구하고 점 집합을 요구하며 임의의 두 점의 거리가 kkk보다 크다(변의 길이는 1)
dp[u][dep]dp[u][dep]dp[u][dep]는 uu가 뿌리 노드인 하위 트리에서 선택한 점의 집중 거리는 uuu의 깊이가 적어도 dep dep dep의 최대 가치임을 나타낸다.
솔직히 이렇게 dp dp dp를 설정하는 건 처음 봤는데 일부분을 한정해서 아이의 결점 간 처리를 편리하게 했습니다.
편리한 처리, k=k+1k=k+1k=k+1
uuuu결점을 선택한 경우 아이의 결점이 뿌리 노드인 나무는 처음부터 모두 선택해야 한다. 거리는 k-1이다.선택하지 않을 경우 아이의 결점 사이의 거리가 kkk보다 커야 한다(이때 k는 이미 k+1이다).
두 번째 상황의 구체적인 계산은 바로 dep dep dep를 매거하는 것이다. 각 dep dep dep에 대해 하나의 점이 이 dep dep dep에 도달해야 한다. 다른 아이들은 어떻게 선택해야 조건을 만족시킬 수 있는지,분명히 x+1+dep≥kx+1+dep≥kx+1+dep≥k 다른 아이들의 결점이 서브트리에 기여한 것은 dp[son] [max(dep-4-1,k-dep-1)] dp[son] [max(dep-1,k-dep-1)] dp[son] [max(dep-3.1,k-3dep-1)]가 존재하기 때문에 이 조건을 만족시키지만 dep-3-1 dep--1을 초과하지 않기 때문에 최소한 우리의 요구는 것이다.
그러나 여기서 계산한 것은 매번 현재의 것만 있다. 예를 들어 적어도 xxx는 xx만 계산했고 x+1x+1x+1이 없기 때문에 계산을 끝내려면 역업데이트가 필요하다.

#include
using namespace std;
vector<int> v;
 
typedef long long ll;
const int maxn = 1e5+5000;
 
int n,k;
int a[maxn],dp[1050][1050];
vector<int>G[maxn];
 
void dfs(int u,int f=-1){
    dp[u][0]=a[u];
    for(auto v:G[u]){
        if(v==f)continue;
        dfs(v,u);
    }
    for(int dep=0;dep<n;dep++){
        if(dep==0){
            for(auto v:G[u]){
                if(v==f)continue;
                dp[u][dep]+=dp[v][k-1];
            }
        }
        else{
            for(auto v:G[u]){
                if(v==f)continue;
                int cur=dp[v][dep-1];
                for(auto other:G[u]){
                    if(other==v||other==f)continue;
                    cur+=dp[other][max(dep-1,k-dep-1)];
                }
                dp[u][dep]=max(dp[u][dep],cur);
            }
        }
    }
    for(int dep=n-1;dep>=0;dep--){
        dp[u][dep]=max(dp[u][dep],dp[u][dep+1]);
    }
}
 
int main(){
    cin>>n>>k;k++;
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n-1;i++){
        int a,b;scanf("%d%d",&a,&b);
        G[a].push_back(b),G[b].push_back(a);
    }
    dfs(1);
    cout<<dp[1][0]<<endl;
}