QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504856#7610. Bus LinespandapythonerWA 61ms22280kbC++235.4kb2024-08-04 16:48:072024-08-04 16:48:07

Judging History

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

  • [2024-08-04 16:48:07]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:22280kb
  • [2024-08-04 16:48:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);

const int logn = 18;
const int maxn = 2e5 + 1000;
const int maxm = 2e5 + 1000;
int n, m;
vector<vector<int>> g;
pair<int, int> busses[maxm];
int bup[maxn][logn];
int sz[maxn];
int c;
int tin[maxn], tout[maxn];
int h[maxn];
int par[maxn];
int up[maxn], up_deg[maxn];
ll dp_down[maxn], dp_up[maxn];
vector<int> busses_graph[maxn];

struct tin_comp {
    bool operator()(int u, int v) const { return tin[u] < tin[v]; }
};

ll sum = 0;
ll great_val[maxn];
ll great_val_sum[maxn];
int total_lca = -1;
set<int, tin_comp> st;

ll result[maxn];


int lca(int u, int v);

void clear() {
    st.clear();
    total_lca = -1;
    sum = 0;
}


void add_vertex(int v) {
    if (st.count(v)) return;
    if (total_lca == -1) total_lca = v;
    else total_lca = lca(total_lca, v);
    auto it = st.insert(v).first;
    sum += great_val_sum[v];
    if (it != st.begin()) {
        int u = *prev(it);
        int t = lca(u, v);
        sum -= great_val_sum[t];
    }
    if (next(it) != st.end()) {
        int u = *next(it);
        int t = lca(u, v);
        sum -= great_val_sum[t];
    }
}



ll get_sum() {
    ll result = sum;
    if (total_lca != -1 and total_lca != 0) {
        result -= great_val_sum[par[total_lca]];
        result += dp_down[total_lca];
    }
    return result;
}

void dfs1(int v, int p) {
    par[v] = bup[v][0] = p;
    for (int i = 1; i < logn; i += 1) {
        bup[v][i] = bup[bup[v][i - 1]][i - 1];
    }
    rep(i, len(g[v])) if (g[v][i] == p) {
        g[v].erase(g[v].begin() + i);
        break;
    }
    sz[v] = 1;
    int mxsz = -1;
    int mxszi = -1;
    rep(i, len(g[v])) {
        int to = g[v][i];
        dfs1(to, v);
        sz[v] += sz[to];
        if (mxsz < sz[to]) {
            mxsz = sz[to];
            mxszi = i;
        }
    }
    if (mxszi != -1) {
        swap(g[v][0], g[v][mxszi]);
    }
}


void dfs2(int v, int mh = 0) {
    tin[v] = c++;
    h[v] = mh;
    for (auto to : g[v]) {
        dfs2(to, mh + 1);
    }
    tout[v] = c;
}


int go_up(int v, int x) {
    rep(i, logn) {
        if ((x >> i) & 1) {
            v = bup[v][i];
        }
    }
    return v;
}


int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    u = go_up(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = logn - 1; i >= 0; i -= 1) {
        if (bup[u][i] != bup[v][i]) {
            u = bup[u][i];
            v = bup[v][i];
        }
    }
    assert(u != v);
    return par[u];
}


void dfs3(int v) {
    for (auto to : g[v]) {
        dfs3(to);
        if (h[up[v]] > h[up[to]]) {
            up[v] = up[to];
        }
    }
    assert(v == 0 or h[up[v]] < h[v]);
    up_deg[up[v]] += 1;
    dp_down[v] = up_deg[v] + 1;
    for (auto to : g[v]) {
        dp_down[v] += dp_down[to];
    }
}



void dfs4(int v, ll sum = 0) {
    sum += great_val[v];
    great_val_sum[v] = sum;
    for (auto to : g[v]) {
        dfs4(to, sum);
    }
}


void dfs6(int);


void dfs5(int v) {
    for (int i = len(g[v]) - 1; i >= 0; i -= 1) {
        clear();
        int to = g[v][i];
        dfs5(to);
    }
    for (int i = 1; i < len(g[v]); i += 1) {
        int to = g[v][i];
        dfs6(to);
    }
    for (auto u : busses_graph[v]) {
        add_vertex(u);
    }
    if (g[v].empty()) add_vertex(v);
    dp_up[v] = n - sz[v] + get_sum();
}


void dfs6(int v) {
    for (auto u : busses_graph[v]) {
        add_vertex(u);
    }
    if (g[v].empty()) add_vertex(v);
    for (auto to : g[v]) dfs6(to);
}


void dfs7(int v) {
    if (v != 0 and up[v] != 0) {
        dp_up[v] += dp_up[up[v]];
    }
    for (auto to : g[v]) dfs7(to);
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n;
    g.assign(n, vector<int>());
    rep(i, n - 1) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> m;
    rep(i, m) {
        int u, v; cin >> u >> v; --u; --v;
        busses[i] = make_pair(u, v);
    }
    dfs1(0, 0);
    c = 0;
    dfs2(0);
    rep(v, n) up[v] = v;
    rep(v, n) up_deg[v] = 0;
    rep(i, m) {
        auto [u, v] = busses[i];
        int t = lca(u, v);
        if (h[up[u]] > h[t]) {
            up[u] = t;
        }
        if (h[up[v]] > h[t]) {
            up[v] = t;
        }
    }
    dfs3(0);
    dp_down[0] = 0;
    rep(v, n) {
        great_val[v] = -dp_down[v];
        for (auto to : g[v]) great_val[v] += dp_down[to];
    }
    dfs4(0);
    rep(i, n) dp_up[i] = 0;
    rep(i, n) busses_graph[i] = {};
    rep(i, m) {
        auto [u, v] = busses[i];
        busses_graph[u].push_back(v);
        busses_graph[v].push_back(u);
    }
    clear();
    dfs5(0);
    dp_up[0] = 0;
    dfs7(0);
    rep(v, n) {
        result[v] = dp_up[v];
        for (auto to : g[v]) {
            result[v] += dp_down[to];
        }
    }
    rep(v, n) cout << result[v] << " ";
    cout << "\n";
    return 0;
}

/*
6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 19928kb

input:

6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4

output:

6 9 9 10 7 7 

result:

ok single line: '6 9 9 10 7 7 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 17920kb

input:

2
1 2
1
1 2

output:

1 1 

result:

ok single line: '1 1 '

Test #3:

score: -100
Wrong Answer
time: 61ms
memory: 22280kb

input:

16384
9137 490
3442 7239
1621 6904
13769 10250
14672 12572
14906 9437
6163 12339
15244 12016
3022 8670
3211 9106
11966 14817
15798 15876
6423 7394
894 7695
13877 1983
16342 15158
13574 15932
15125 10722
6989 15683
10335 8801
12301 4246
6166 3893
9347 12073
7897 12195
6510 3101
4526 15385
7017 7001
4...

output:

32747 -287821865 -281402325 -281348504 -287847358 -289794241 -281420229 -365404712 -281384377 -287954327 -287742505 -281348486 -287847446 -289043037 -281384410 -281348479 -287837060 -281348525 -289192412 -281367833 -288953757 -281634652 -281348502 -287760431 -281402357 -288123725 -287750130 -2891905...

result:

wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '32747 -287821865 -281402325 -2...91542479 -287742310 -281348325 '