QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504895#7610. Bus LinespandapythonerWA 61ms24448kbC++235.5kb2024-08-04 17:04:222024-08-04 17:04:22

Judging History

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

  • [2024-08-04 17:04:22]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:24448kb
  • [2024-08-04 17:04:22]
  • 提交

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];
    int a = -1;
    int b = -1;
    if (it != st.begin()) {
        a = *prev(it);
        int t = lca(a, v);
        sum -= great_val_sum[t];
    }
    if (next(it) != st.end()) {
        b = *next(it);
        int t = lca(b, v);
        sum -= great_val_sum[t];
    }
    if (a != -1 and b != -1) {
        sum += great_val_sum[lca(a, b)];
    }
}



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);
}


void solve() {
    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];
        }
    }
}

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);
    }
    solve();
    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: 17908kb

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: 2ms
memory: 17968kb

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: 24448kb

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 33980 34007 34086 33923 33905 34017 42189 34041 33910 33993 34104 34004 33988 34008 34111 33998 34065 33811 50416 33991 33865 34088 33981 33975 33761 34059 34043 34288 33666 49981 34072 33791 33807 34243 34241 33996 50680 34076 34191 34084 33968 33998 34288 34104 34241 33988 34052 33962 34119 ...

result:

wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '32747 33980 34007 34086 33923 ... 34256 33754 33235 34188 34265 '