Submission #1083484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083484		Requiem	Chase (CEOI17_chase)	C++17	100 / 100	236 ms	163380 KiB

chase

#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define ii pair<int, int>
#define iii pair<int, ii>
#define pb push_back
#define fi first
#define se second
#define MASK(i) (1LL << i)
#define BIT(x, i) (((x) >> (i))&1)
#define TASKNAME "chase"
using namespace std;

/**
Cho cay n dinh va so o banh mi v.

Dinh i co chua pi con chim bo cau.

Khi dung 1 o banh mi o dinh u thi nhung con chim bo cau o cac dinh ke u se di den u.


Tim 1 duong di đơn u1, u2, ..., uk. Gọi sumN(ui) la tong cua nhung dinh lien ke ui ma khong nam tren duong di
ma ta rải bánh mì thì kết quả của ta là:
sumN(ui).

v <= 100
n <= 1e5.

subtask 1: n <= 10.

subtask 2: n <= 1000.

Nhận xét: ta có n^2 đường đi.
Giả sử ta xuất phát từ đỉnh i.
Ta chỉ cần dùng thêm dp[u][v][1]: xét đến đỉnh u, ta đã dùng v ổ bánh mì và liệu đỉnh bố
có dùng bánh mì không.

subtask 3: 1 đường đi xuất phát ở 1. Giải như subtask 2
subtask 4: n <= 1e5.
Ta cần giải trong O(N.v)

Ta giải kiểu gì nhỉ.
Bây giờ ta không thể thay đổi gốc thì chắc ta phải tìm cách giải bài toán trong cây con gốc u.

Nhận xét của ta là đi lên hay đi xuống không quan trọng Với 1 đường đi thì thứ quan trọng là những
vị trí ta rải bánh mì.

Nhận xét của ta là: nếu ta đi qua đỉnh u thì kết quả của ta sẽ phụ thuộc vào kết quả của đỉnh v1 và v2
mà ta chọn

Ta muốn đường đi của ta phải đi qua u:
- Có các trường hợp sau: đường đi thẳng lên từ u.
- đường đi thẳng lên u từ v1 xong đi xuống v2.

gọi up[v][j]: đường đi có trọng số lớn nhất lên v chỉ trong cây con gốc v.
dp[u][j] = up[v1][j1] + up[v2][j2] + pv (v khac v1, v khac v2, j = j1 + j2 + 1).
up[u][j] = max(up[v][j] + ...)
chắc khoảng n * v ^ 2.
**/

template<typename T> bool maximize(T &a, T b){  if (a < b) { a= b; return true; } else return false;}
const int MAXN = 3e5 + 9;
vector<int> g[MAXN];
int p[MAXN];
int n, numBread;

namespace subtask1{
    bool check(){
         return n <= 1000;
    }

    int dp[1003][103], ans = 0;

    void dfs(int u, int pa){

        int sumNeighbour = 0;
        for(int v: g[u]){
            if (v == pa) continue;
            sumNeighbour += p[v];
        }

        for(int v: g[u]){
            if (v == pa) continue;
            FOR(j, 0, numBread){
                maximize(dp[v][j], dp[u][j]);
                maximize(dp[v][j + 1], dp[u][j] + sumNeighbour); //voi nhung thang da di qua thi sumNeighbor se
                                                                 //khong co tac dung gi nhung sumNeighbor co the
                                                                 //lam giam trong so cua thg Jerry.
                maximize(ans, dp[v][j]);
                if (j + 1 <= numBread) maximize(ans, dp[v][j + 1]);
            }
            dfs(v, u);
        }
    }
    void solve(){
        FOR(i, 1, n){
            FOR(j, 1, n){
                FOR(t, 1, numBread){
                    dp[j][t] = 0;
                }
            }
            dfs(i, -1);
        }
        printf("%lld\n", ans);
    }
}

namespace subtask2{
    bool check(){
        return true;
    }

    /**
    dp[u][i]: duong di di qua dinh u.
    tu subtask 1, ta thay dp[v][i] = max(dp[u][i], dp[u][i - 1] + sumNeighBor[u])

    Ta định nghĩa laij SumNeighBor[u]: tong nhung dinh v ke u
    Gia su ta muon duong di cua minh phai di qua u.

    Các trường hợp đường thẳng:
       Ta có các trường hợp: Duong di xuat phat tu u.
       Trường hợp tiếp theo: xuất phát từ 1 đình nằm trong cây con của u.
    trường hợp ghép:
       Đi lên từ 1 đỉnh trong u và đi xuống từ 1 đỉnh trong v.

    Trước hết, ta gọi up[u][j]: dường đi xuất phát từ u đi lên đỉnh u và đã sử dụng j ổ bánh mì
                      down[u][j]: đường đi xuất phát từ u đi xuống 1 đỉnh trong cây con gốc u và ....

    down[u][j] = max(down[v][j], down[v][j - 1] + sumNeighBor[u] - p[parU])
    up[u][j] = max(up[v][j], up[v][j - 1] + sumNeighBor[u] - p[v]).
    Trạng thái kết hợp:

    Với đỉnh u:
    up[v1][j] + down[v2][k] + sumNeighbor[u] - p[v1]. Neu u rai banh mi
    up[v1][j] + down[v2][k] neu u khong rai banh mi.

    Khi giải mấy bài đường đi như này thì có 2 kiểu:
    - centroid
    - dp trên cây, cố định đường đi qua gốc đó.
    Bài này ta dựa vào up và down là các đường đi xuất phát và đi lên u.
    **/

    int up[MAXN][102], down[MAXN][102], sumNeighbor[MAXN];
    int mxDown[102], ans = 0;
    void dfs(int u, int pa){
        for(int v: g[u]){
            sumNeighbor[u] += p[v];
        }
        for(int v: g[u]){
            if (v == pa) continue;
            dfs(v, u);
            FOR(j, 0, numBread){
                maximize(down[u][j], down[v][j]);
                if (j > 0) {
                    maximize(down[u][j], down[v][j - 1] + sumNeighbor[u] - p[pa]);
                    maximize(ans, down[v][j - 1] + sumNeighbor[u]);
                }
                if (j > 0) maximize(down[u][j], down[u][j - 1]);
            }

            FOR(j, 0, numBread){
                maximize(up[u][j], up[v][j]);
                if (j > 0) maximize(up[u][j], up[v][j - 1] + sumNeighbor[u] - p[v]);
                if (j > 0) maximize(up[u][j], up[u][j - 1]);
            }
        }
        maximize(up[u][1], sumNeighbor[u]);
        FOR(i, 0, numBread) {
            maximize(ans, down[u][i]);
            maximize(ans, up[u][i]);
        }

        for(int v: g[u]){
            if (v != pa){
                FOR(j, 0, numBread){
                    maximize(ans, mxDown[j] + up[v][numBread - j]);
                    if (numBread - j - 1 >= 0) {
                        maximize(ans, mxDown[j] + up[v][numBread - j - 1] + sumNeighbor[u] - p[v]);
                    }
                }
                FOR(j, 0, numBread){
                    maximize(mxDown[j], down[v][j]);
                }

            }
        }
        FOR(j, 0, numBread){
            mxDown[j] = 0;
        }
        reverse(g[u].begin(), g[u].end());
        for(int v: g[u]){
            if (v != pa){
                FOR(j, 0, numBread){
                    maximize(ans, mxDown[j] + up[v][numBread - j]);
                    if (numBread - j - 1 >= 0) {
                        maximize(ans, mxDown[j] + up[v][numBread - j - 1] + sumNeighbor[u] - p[v]);
                    }
                }
                FOR(j, 0, numBread){
                    maximize(mxDown[j], down[v][j]);
                }

            }
        }
        FOR(j, 0, numBread){
            mxDown[j] = 0;
        }
//        printf("CUR %lld %lld\n", u, ans);
//
//        printf("UP \n");
//        FOR(i, 0, numBread){
//            printf("%lld ", up[u][i]);
//        }
//        printf("\nDOWN \n");
//
//        FOR(i, 0, numBread){
//            printf("%lld ", down[u][i]);
//        }
//        printf("\n");
    }
    void solve(){
        dfs(1, -1);
        printf("%lld\n", ans);
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> numBread;
    FOR(i, 1, n){
        cin >> p[i];
    }
    FOR(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

//    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
}

Compilation message (stderr)

chase.cpp:229:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  229 | main(){
      | ^~~~
chase.cpp: In function 'int main()':
chase.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:233:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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