QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224029#5418. Color the TreeluanmengleiWA 25ms11608kbC++172.8kb2023-10-22 23:13:102023-10-22 23:13:10

Judging History

你现在查看的是最新测评结果

  • [2023-10-22 23:13:10]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:11608kb
  • [2023-10-22 23:13:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED debug("PASSED (%s) LINE #%s", __FUNCTION__, __LINE__)

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (x > y) x = y; }

const int N = 1e5 + 10;
int n, a[N], dfn[N], cnt, len[N], son[N], dep[N], lg2[N], st[18][N];
i64 f[N], g[N];
vector<int> G[N];

void dfs1(int x, int fa) {
    len[x] = 1, son[x] = 0;
    for (int y : G[x]) if (y != fa) {
        dep[y] = dep[x] + 1;
        dfs1(y, x);
        chkmax(len[x], len[y] + 1);
        if (!son[x] || len[son[x]] < len[y])
            son[x] = y;        
    }
}

void init_st() {
    for (int i = 0; i < n; i ++)
        st[0][i] = a[i];
    for (int i = 1; i < 18; i ++)
        for (int j = 0; j + (1 << i) - 1 < n; j ++)
            st[i][j] = st[i - 1][j], chkmin(st[i][j], st[i - 1][j + (1 << (i - 1))]);
}

i64 query_st(int l, int r) {
    if (l > r)
        return 1e18;
    int k = lg2[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

void dfs2(int x, int fa) {
    dfn[x] = ++ cnt;
    if (son[x])
        dfs2(son[x], x);
    for (int y : G[x]) if (y != fa && y != son[x])
        dfs2(y, x);
}

void dp(int x, int fa) {
    for (int y : G[x]) if (y != fa)
        dp(y, x);

    f[dfn[x]] = a[0], g[dfn[x]] = 0;
    for (int y : G[x]) if (y != fa && y != son[x]) {
        for (int i = 1; i <= len[y]; i ++) {
            if (g[dfn[x] + i] < i) {
                chkmin(f[dfn[x] + i], query_st(g[dfn[x] + i] + 1, i));
                g[dfn[x] + i] = i;
            }
            f[dfn[x] + i] += min(f[dfn[y] + i - 1], query_st(g[dfn[y] + i - 1], i - 1));
        }
    }
}

void solve() {
	cin >> n;
    cnt = 0;
    for (int i = 1; i <= n; i ++) {
        G[i].clear();
        g[i] = 0, f[i] = 1e18;
    }
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    for (int i = 2, x, y; i <= n; i ++) {
        cin >> x >> y;
        G[x].push_back(y), G[y].push_back(x);
    }
    dep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 0);
    init_st();
    dp(1, 0);
    i64 ans = 0;
    for (int i = 1; i <= len[1]; i ++) {
        ans += min(f[i], query_st(g[i], i - 1));
    }
    cout << ans << "\n";
}

signed main() {
    for (int i = 2; i < N; i ++) {
        lg2[i] = lg2[i / 2] + 1;
    }
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
    while (tt --)
        solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10224kb

input:

3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4

output:

35
17
1218

result:

ok 3 number(s): "35 17 1218"

Test #2:

score: -100
Wrong Answer
time: 25ms
memory: 11608kb

input:

3000
54
43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44
1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28...

output:

185
170
222
230
156
255
225
126
100
81
155
73
154
134
149
144
228
230
140
191
155
171
78
282
195
286
195
211
119
197
211
252
88
252
239
241
173
180
195
145
109
149
180
188
226
210
182
97
199
59
56
31
115
224
203
172
155
217
53
143
189
174
173
137
233
105
163
273
80
350
156
133
147
159
240
269
147
22...

result:

wrong answer 1st numbers differ - expected: '180', found: '185'