제출 #1026881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026881		12345678	Chase (CEOI17_chase)	C++17	100 / 100	1167 ms	180084 KiB

chase

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=105;

#define ll long long

ll n, k, b[nx], u, v, sm[nx], dp[nx][kx], dpr[nx][kx], res, sz[nx], used[nx], mx[nx];
vector<ll> d[nx];

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfsadd(int u, int p)
{
    for (int i=1; i<=k; i++) dp[u][i]=max(dp[p][i], dp[p][i-1]+sm[u]-b[p]), mx[i]=max(mx[i], dp[u][i]);
    for (auto v:d[u]) if (v!=p&&!used[v]) dfsadd(v, u);
}

void dfsquery(int u, int p)
{
    for (int i=1; i<=k; i++) dpr[u][i]=max(dpr[p][i], dpr[p][i-1]+sm[p]-b[u]), res=max(res, dpr[u][i]+mx[k-i]);
    for (int i=0; i<k; i++) res=max(res, dpr[u][i]+sm[u]+mx[k-i-1]);
    for (auto v:d[u]) if (v!=p&&!used[v]) dfsquery(v, u);
}

void decomposition(int u)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    for (int i=0; i<=k; i++) mx[i]=dp[u][i]=dpr[u][i]=0;
    for (int i=0; i<d[u].size(); i++) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
    res=max(res, mx[k-1]+sm[u]);
    for (int i=0; i<=k; i++) mx[i]=0;
    for (int i=(int)d[u].size()-1; i>=0; i--) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
    for (auto v:d[u]) if (!used[v]) decomposition(v);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>b[i];
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u), sm[u]+=b[v], sm[v]+=b[u];
    if (k==0) return cout<<0, 0;
    decomposition(1);
    cout<<res;
}

컴파일 시 표준 에러 (stderr) 메시지

chase.cpp: In function 'void decomposition(int)':
chase.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0; i<d[u].size(); i++) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
      |                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30