Submission #4353804


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct TreeDiameter {
    int N; vector<set<int>> E;TreeDiameter() {} TreeDiameter(int _N) { init(_N); }
    void init(int _N) { N = _N; E.resize(N); }
    void add_edge(int a, int b) { E[a].insert(b); E[b].insert(a); }
    void build() {
        vector<int> dv(N), dw(N); rep(i, 0, N) dv[i] = 0; dfs(0, -1, dv); v = 0;
        rep(i, 0, N) if (dv[i] > dv[v]) v = i; rep(i, 0, N) dv[i] = 0; dfs(v, -1, dv); w = 0;
        rep(i, 0, N) if (dv[i] > dv[w]) w = i; rep(i, 0, N) dw[i] = 0; dfs(w, -1, dw); dia = dv[w];
        if (dia % 2 == 0) {
            int R = dia / 2; rep(i, 0, N) if (dv[i] == R && dw[i] == R) cent_even = i;
            vector<int> dc(N, 0); dfs(cent_even, -1, dc); rep(i, 0, N) if (dc[i] == R)leaf_even.push_back(i);
        }
        else {
            int R = dia / 2; int c1 = 0, c2 = 0; rep(i, 0, N) if (dv[i] == R && dw[i] == R + 1) c1 = i;
            rep(i, 0, N)if (dv[i] == R + 1 && dw[i] == R) c2 = i; cent_odd = { c1, c2 }; vector<int> dc1(N, 0);
            dfs(c1, -1, dc1); vector<int> dc2(N, 0); dfs(c2, -1, dc2);
            rep(i, 0, N) if (dc1[i] == R && dc2[i] == R + 1) leaf_odd.first.push_back(i);
            rep(i, 0, N) if (dc1[i] == R + 1 && dc2[i] == R) leaf_odd.second.push_back(i);
        }
        vector<int> cn(N); dfs2(0, -1, cn); int mi = N + 1;
        rep(i, 0, N) {
            int d = N - cn[i]; fore(to, E[i]) if (cn[to] < cn[i]) d = max(d, cn[to]);
            if (d < mi) { mi = d; centroid.clear(); centroid.push_back(i); }
            else if (d == mi)centroid.push_back(i);
        }
    }
    void dfs(int cu,int pa,vector<int>& D){fore(to,E[cu])if(to!=pa){D[to]=D[cu]+1;dfs(to, cu, D);}}
    void dfs2(int cu,int pa,vector<int>& cn){cn[cu]=1;fore(to,E[cu])if(to!=pa){dfs2(to,cu,cn);cn[cu]+=cn[to];}}

    // out
    int v, w, dia;
    int cent_even; vector<int> leaf_even;
    pair<int, int> cent_odd; pair<vector<int>, vector<int>> leaf_odd;
    vector<int> centroid;
};
// vid : id -> vid          head, heavy, parent : unused
// depth : id -> depth      inv : vid -> id
// in(vid), out(vid) : for euler tree [in[v], out[v])
struct HLDecomposition {
    vector<set<int>> g; vector<int> vid, head, heavy, parent, depth, inv, in, out;
    HLDecomposition() {} HLDecomposition(int n) { init(n); }
    void init(int n) {
        g.resize(n); vid.resize(n, -1); head.resize(n); heavy.resize(n, -1);
        parent.resize(n); depth.resize(n); inv.resize(n); in.resize(n); out.resize(n);
    }
    void add(int u, int v) { g[u].insert(v); g[v].insert(u); } void build() { dfs(0, -1); t = 0; dfs_hld(); }

    int dfs(int curr, int prev) {
        parent[curr] = prev; int sub = 1, max_sub = 0;
        heavy[curr] = -1;
        for (int next : g[curr]) if (next != prev) {
            depth[next] = depth[curr] + 1;
            int sub_next = dfs(next, curr); sub += sub_next;
            if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
        }return sub;
    }

    int t = 0;
    void dfs_hld(int v = 0)
    {
        vid[v] = in[v] = t;
        t++;
        inv[in[v]] = v;
        if (0 <= heavy[v]) {
            head[heavy[v]] = head[v];
            dfs_hld(heavy[v]);
        }
        for (auto u : g[v]) if (depth[v] < depth[u])  if (u != heavy[v]) {
            head[u] = u;
            dfs_hld(u);
        }
        out[v] = t;
    }


    void foreach(int u, int v, function<void(int, int)> f) { // [x,y]
        if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]);
        if (head[u] != head[v]) foreach(u, parent[head[v]], f);
    }
    int ancestor(int from, int times) {
        while (true) {
            if (depth[head[from]] > depth[from] - times) {
                times -= depth[from] - depth[head[from]] + 1; if (head[from] == 0)return -1; from = parent[head[from]];
            }
            else return inv[vid[from] - times];
        }
    }
    int lca(int u, int v) {
        if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u;
        return lca(u, parent[head[v]]);
    }
    int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
    int child(int parent, int child, int times) {
        assert(depth[parent] < depth[child]);
        int d = distance(parent, child); assert(times - 1 <= d); return ancestor(child, d - times);
    }
    int go(int from, int to, int times) {
        int d = distance(from, to); assert(0 <= times and times <= d);
        int lc = lca(from, to); if (lc == to)return ancestor(from, times); if (lc == from)return child(from, to, times);
        int dd = distance(from, lc); if (dd <= times)return go(lc, to, times - dd); return ancestor(from, times);
    }
};
template<class V> struct BIT {
    BIT() {}  // [L, R)
    int NV;vector<V> bit;
    BIT(int n){ init(n); }
    void init(int n) { NV = 1; while (NV < n)NV *= 2; bit.resize(NV); clear(); }
    V operator[](int e) { V s = 0; e++; while (e) s += bit[e - 1], e -= e&-e; return s; }
    void add(int e, V v) { e++; while (e <= NV) bit[e - 1] += v, e += e&-e; }
    int lower_bound(V val) { 
        V tv = 0; int i, ent = 0; for (i = NV - 1; i >= 0; i--)
        if(tv+bit[ent+(1<<i)-1]<=val)tv+=bit[ent+(1<<i)-1],ent += (1 << i);return ent;
    }
    V get(int L, int R) {
        assert(0 <= L); assert(R <= NV); assert(L <= R);
        V res = 0; if(R) res += operator[](R - 1); if (L) res -= operator[](L - 1);return res;
    }
    void clear() { rep(i, 0, NV) bit[i] = 0; }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/






//---------------------------------------------------------------------------------------------------
void solve(TreeDiameter &td, HLDecomposition &hld, int N, vector<ll> &dist) {
    rep(i, 0, N) {
        ll d = -1;
        if (td.dia % 2 == 0) {
            chmax(d, (ll)hld.distance(i, td.leaf_even[0]));
            chmax(d, (ll)hld.distance(i, td.leaf_even[1]));
        }
        else {
            chmax(d, (ll)hld.distance(i, td.leaf_odd.first[0]));
            chmax(d, (ll)hld.distance(i, td.leaf_odd.second[0]));
        }
        dist[i] = d;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int N, M;

    cin >> N;
    TreeDiameter td1; td1.init(N);
    HLDecomposition hld1; hld1.init(N);
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        td1.add_edge(a, b);
        hld1.add(a, b);
    }
    td1.build();
    hld1.build();

    cin >> M;
    TreeDiameter td2; td2.init(M);
    HLDecomposition hld2; hld2.init(M);
    rep(i, 0, M - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        td2.add_edge(a, b);
        hld2.add(a, b);
    }
    td2.build();
    hld2.build();

    ll ma = -1;
    chmax(ma, 1LL * td1.dia);
    chmax(ma, 1LL * td2.dia);

    vector<ll> dist1(N), dist2(M);
    solve(td1, hld1, N, dist1);
    solve(td2, hld2, M, dist2);

    BIT<ll> bit1(101010), bit2(101010);
    rep(i, 0, N) bit1.add(dist1[i], 1);
    rep(i, 0, M) bit2.add(dist2[i], 1);
    ll other = 0;

    ll ans = 0;
    rep(i, 0, N) {
        ll ng = 0;
        if(0 <= ma - dist1[i]-1) bit2.get(0, ma - dist1[i]-1);
        other += ng;
        ans += dist1[i] * (M - ng);
    }
    rep(i, 0, M) {
        ll ng = 0;
        if (0 <= ma - dist2[i]-1) bit1.get(0, ma - dist2[i]-1);
        other += ng;
        ans += dist2[i] * (N - ng);
    }
    ans += ma * other / 2;
    ans += 1LL * (1LL * N * M - other / 2);
    cout << ans << endl;
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 8854 Byte
Status
Exec Time 446 ms
Memory 86880 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 0 / 700 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt
Case Name Status Exec Time Memory
01.txt 2 ms 2304 KB
02.txt 2 ms 2304 KB
11.txt 2 ms 2304 KB
12.txt 2 ms 2304 KB
13.txt 2 ms 2304 KB
14.txt 2 ms 2304 KB
15.txt 2 ms 2304 KB
16.txt 2 ms 2304 KB
17.txt 2 ms 2304 KB
18.txt 2 ms 2304 KB
19.txt 2 ms 2304 KB
20.txt 2 ms 2304 KB
21.txt 439 ms 66400 KB
22.txt 376 ms 66784 KB
23.txt 366 ms 66784 KB
24.txt 380 ms 82664 KB
25.txt 446 ms 67168 KB
26.txt 360 ms 66792 KB
27.txt 409 ms 82656 KB
28.txt 356 ms 66784 KB
29.txt 402 ms 83168 KB
30.txt 420 ms 86880 KB
31.txt 355 ms 66792 KB
32.txt 380 ms 66784 KB
33.txt 352 ms 66408 KB
34.txt 381 ms 86752 KB
35.txt 373 ms 66792 KB
36.txt 363 ms 67176 KB
37.txt 375 ms 78056 KB
38.txt 353 ms 67176 KB
39.txt 384 ms 80864 KB
40.txt 431 ms 82656 KB
41.txt 191 ms 34784 KB
42.txt 177 ms 34792 KB
43.txt 191 ms 34792 KB
44.txt 203 ms 34784 KB
45.txt 224 ms 34784 KB
46.txt 213 ms 34792 KB
47.txt 249 ms 54112 KB
48.txt 197 ms 34784 KB
49.txt 238 ms 45664 KB
50.txt 208 ms 45672 KB