Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int T, n, u, v, h[N], e[N], ne[N], idx;
int ans[N], down[N], f[N], up[N];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
void update(int x, int &a, int &b) {
    if (x > a) b = a, a = x;
    else if (x > b) b = x;
}
void push_up(int x, int &a, int &b, int &c) {
    if (x > a) c = b, b = a, a = x;
    else if (x > b) c = b, b = x;
    else if (x > c) c = x;
}
void dfs(int u) {
    int a = 0, b = 0; // 最远、次远距离
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        dfs(v);
        update(down[v] + 1, a, b); // 向下最远距离
        f[u] = max(f[u], f[v]);
    }
    down[u] = a;
    f[u] = max(f[u], a + b); // 子树直径
}
void dfs2(int u) {
    int lf = 0, rf = 0, ld = -1, md = -1, rd = -1, res = ans[u]; // 向上子树最长直径
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        ans[u] = max(ans[u], f[v]);
        update(f[v], lf, rf); // 子树最长、次长直径
        push_up(down[v], ld, md, rd); // 子节点向下最远距离
    }
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        up[v] = max(up[u] + 1, ld == down[v] ? md + 2 : ld + 2); // 向上最远距离
        ans[v] = max({res, lf == f[v] ? rf : lf, (ld == down[v] ? md : ld) + up[u] + 1});
        if (ld == down[v]) ans[v] = max(ans[v], md + rd + 2);
        else if (md == down[v]) ans[v] = max(ans[v], ld + rd + 2);
        else ans[v] = max(ans[v], ld + md + 2);
        dfs2(v);
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int s = (n + 1) * 4;
        memset(h, 0, s);
        memset(f, 0, s);
        memset(down, 0, s);
        memset(up, 0, s);
        memset(ans, 0, s);
        idx = 0;
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        dfs(1);
        dfs2(1);
        for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int N = 6001;
int u, v, r[N], h[N], e[N], ne[N], idx, d[N];
int n, root, f[N][2];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &r[i]);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &v, &u);
        add(u, v);
        ++d[v];
    }
    for (int i = 1; i <= n; ++i)
        if (!d[i]) {
            root = i;
            break;
        }
    dfs(root);
    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int N = 3001, M = 3000;
int u, x, ww, h[N], w[M], e[M], ne[M], idx;
int n, m, v[N], f[N][N];
void add(int u, int v, int ww) {
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
int dfs(int x) {
    if (x > n - m) {
        f[x][1] = v[x];
        return 1;
    }
    int sum = 0;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        int s = dfs(y);
        sum += s;
        for (int j = sum; j; --j)
            for (int k = 1; k <= s; ++k)
                if (j >= k) f[x][j] = max(f[x][j], f[x][j - k] + f[y][k] - w[i]);
    }
    return sum;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(f, -0x3f3f3f, sizeof f);
    register int i = 1;
    for (; i <= n - m; ++i) {
        scanf("%d", &x);
        for (int j = 1; j <= x; ++j) {
            scanf("%d%d", &u, &ww);
            add(i, u, ww);
        }
    }
    for (; i <= n; ++i) {
        scanf("%d", &v[i]);
    }
    for (i = 1; i <= n; ++i) f[i][0] = 0;
    dfs(1);
    for (i = m; i; --i)
        if (f[1][i] >= 0) {
            printf("%d\n", i);
            break;
        }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int N = 1001, M = 2002;
int u, h[N], e[M], ne[M], idx;
int n, ans = N, s[N];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
int dfs(int u, int f) {
    int res = 0, idx = 0, c[999] = {0};
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        c[idx++] = dfs(v, u);
    }
    sort(c, c + idx, greater<int>());
    for (int i = 0; i < idx; ++i)
        res = max(res, c[i] + i);
    return res + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &u);
        add(u, i), add(i, u);
    }
    for (int i = 1; i <= n; ++i) {
        s[i] = dfs(i, 0);
        ans = min(ans, s[i]);
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i)
        if (s[i] == ans)
            printf("%d ", i);
    puts("");
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int N = 301, M = 302;
int u, v, h[N], e[N], ne[N], idx;
int n, m;
int dp[N][M];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
int dfs(int u) {
    int sum = 2;
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        int s = dfs(v);
        sum += s;
        for (int j = min(m, sum); j; --j)
            for (int k = 0; k < min(j, s); ++k)
                dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k]);
    }
    return sum;
}
int main() {
    scanf("%d%d", &n, &m);
    ++m;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &u, &dp[i][1]);
        add(u, i);
    }
    dfs(0);
    printf("%d\n", dp[0][m]);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 202;
int u, v, ww, h[N], e[M], ne[M], w[M], idx;
int n, t;
int dp[N][N];
void add(int u, int v, int ww) {
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
int dfs(int u, int f) {
    int sum = 0;
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        int s = dfs(v, u);
        sum += s + 1;
        for (int j = min(sum, t); j; --j)
            for (int k = min(s, j - 1); k >= 0; --k)
                dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - k - 1] + w[i]);
    }
    return sum;
}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d%d", &u, &v, &ww);
        add(u, v, ww);
        add(v, u, ww);
    }
    dfs(1, 0);
    printf("%d\n", dp[1][t]);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 1, M = 2 * N;
int n, u, v, ww;
int c[N], h[N], w[M], e[M], ne[M], idx;
LL dist[N], sz[N], ans;
void add(int u, int v, int ww) {
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d%d", &u, &v, &ww);
        add(u, v, ww), add(v, u, ww);
    }
    function<LL(int, int)> dfs = [&](int u, int f) {
        LL cnt = c[u];
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                LL s = dfs(v, u);
                dist[u] += dist[v] + w[i] * s;
                cnt += s;
            }
        }
        return sz[u] = cnt;
    };
    dfs(1, 0);
    ans = dist[1];
    function<void(int, int)> dp = [&](int u, int f) {
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                // dist[v] = dist[u] + (sz[1] - sz[v]) * w[i] - sz[v] * w[i];
                dist[v] = dist[u] + (sz[1] - sz[v] - sz[v]) * w[i];
                ans = min(ans, dist[v]);
                dp(v, u);
            }
        }
    };
    dp(1, 0);
    printf("%lld\n", ans);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101, M = 2 * N;
int n, u, v, h[N], w[M], e[M], ne[M], idx;
int ans = 1e9;
bool visited[N];
struct node {
    int u, s;
    node() {}
    node(int idx, int step) : u(idx), s(step) {}
};
node q[N];
void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int bfs(int x) {
    int sum = 0;
    memset(visited, false, n + 1);
    visited[x] = true;
    int hh = 0, tt = -1;
    q[++tt] = node(x, 1);
    while (hh <= tt) {
        auto[u, s] = q[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (visited[v]) continue;
            q[++tt] = node(v, s + 1);
            visited[v] = true;
            sum += w[v] * s;
        }
    }
    return sum;
}
int main() {
    scanf("%d", &n);
    memset(h, -1, (n + 1) * 4);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &w[i], &u, &v);
        if (u) add(i, u), add(u, i);
        if (v) add(i, v), add(v, i);
    }
    for (int i = 1; i <= n; ++i) ans = min(ans, bfs(i));
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 101, INF = INT_MAX;
int ans = INF;
int d[N][N];
int n, u, v, w[N];
int main() {
    scanf("%d", &n);
    fill(d[0], d[0] + N * N, INF);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &w[i], &u, &v);
        if (u) d[i][u] = d[u][i] = 1;
        if (v) d[i][v] = d[v][i] = 1;
    }
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (d[i][k] < INF && d[k][j] < INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int j = 1; j <= n; ++j)
            if (i != j)
                sum += w[j] * d[i][j];
        ans = min(ans, sum);
    }
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 2 * N;
int n, u, v, h[N], w[M], e[M], ne[M], idx;
int ans = 1e9;
bool visited[N];
void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int dfs(int u, int s) {
    int sum = s * w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (visited[v]) continue;
        visited[v] = true;
        sum += dfs(v, s + 1);
    }
    return sum;
}
int main() {
    scanf("%d", &n);
    memset(h, -1, (n + 1) * 4);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &w[i], &u, &v);
        if (u) add(i, u), add(u, i);
        if (v) add(i, v), add(v, i);
    }
    for (int i = 1; i <= n; ++i) {
        memset(visited, false, n + 1);
        visited[i] = true;
        ans = min(ans, dfs(i, 0));
    }
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 2 * N;
int n, u, v, h[N], w[M], e[M], ne[M], idx;
int deep[N], dist[N], sum[N];
int ans;
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
void dfs(int u, int f) {
    deep[u] = deep[f] + 1;
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        dfs(v, u);
        sum[u] += sum[v];
    }
}
int dp(int u, int f) {
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        dist[v] = dist[u] + sum[1] - sum[v] - sum[v];
        ans = min(ans, dist[v]);
        dp(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (register int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &w[i], &u, &v);
        sum[i] = w[i];
        if (u) add(i, u), add(u, i);
        if (v) add(i, v), add(v, i);
    }
    deep[0] = 0;
    dfs(1, 0);
    for (register int i = 1; i <= n; ++i)
        dist[1] += (deep[i] - 1) * w[i];
    ans = dist[1];
    dp(1, 0);
    printf("%d\n", ans);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 50001, M = 2 * N;
int n, u, v, h[N], e[M], ne[M], idx;
int results[N], k, ans = N;
void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int dfs(int u, int f) {
    int res = 0, sum = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        int s = dfs(v, u);
        res = max(res, s);
        sum += s;
    }
    res = max(res, n - sum);
    if (res < ans) {
        ans = res;
        k = 0;
        results[k++] = u;
    } else if (res == ans) {
        results[k++] = u;
    }
    return sum;
}
int main() {
    scanf("%d", &n);
    memset(h, -1, (n + 1) * 4);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(1, -1);
    sort(results, results + k, greater<int>());
    while (k--) printf("%d ", results[k]);
    printf("\n");
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20001, M = 2 * N;
int t, n, u, v, h[N], e[M], ne[M], idx;
bool visited[N];
int ans, node;
void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int dfs(int u) { // return size of the tree `u`.
    visited[u] = true;
    int res = 0, // max size of connected componet.
       sum = 1; // size of current tree (whose root node is `u`).
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (visited[v]) continue;
        int s = dfs(v);
        res = max(res, s);
        sum += s;
    }
    res = max(res, n - sum);
    if (res < ans) {
        ans = res;
        node = u;
    }
    return sum;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        idx = 0, ans = n;
        memset(h, -1, (n + 1) * 4);
        memset(visited, false, n + 1);
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            add(u, v), add(v, u);
        }
        dfs(1);
        printf("%d %d\n", node, ans);
    }
    return 0;
}
0%