QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224002#5418. Color the TreeluanmengleiWA 26ms12300kbC++172.9kb2023-10-22 22:53:132023-10-22 22:53:14

Judging History

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

  • [2023-10-22 22:53:14]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:12300kb
  • [2023-10-22 22:53:13]
  • 提交

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 <= lg2[n]; 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) {
    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 ++) {
            f[dfn[x] + i] += f[dfn[y] + i - 1];
        }
    } 
    // for (int i = 0; i < len[x]; i ++)
        // chkmin(f[dfn[x] + i], a[i]);
    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;
        }
    }
}

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 ++) {
        if (g[i] < i - 1) {
            chkmin(f[i], query_st(g[i] + 1, i - 1));
        }
        ans += f[i];
    }
    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: 0ms
memory: 10212kb

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: 26ms
memory: 12300kb

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:

180
134
222
222
156
255
225
126
100
79
139
73
140
127
143
119
228
179
131
171
128
171
78
282
195
286
152
200
119
188
209
213
88
252
207
206
160
179
184
144
109
148
180
169
226
210
182
85
162
59
56
31
115
216
201
144
155
212
53
155
189
134
173
134
216
106
163
255
80
339
156
133
129
156
219
269
148
22...

result:

wrong answer 2nd numbers differ - expected: '168', found: '134'