FULL

 avatar
unknown
c_cpp
3 years ago
6.7 kB
5
Indexable
        diam_parent[v] = diam_parent[p];
    dp[v].add(0);
    for (auto to : g[v])
    {
        if (in_DIAM[to] || to == p)
            continue;
        dfs(to, v);
        dp[v].add(dp[to]);
    }
}
void calc_self(int v, int p, int k = 0)
{
    sz[v] = 1;
    self_val[v] = max(self_val[v], dp[v].diam);
    self_val[v] = max(self_val[v], k);
    k_max maxs = k_max(2), kek = k_max(3);
    for (auto to : g[v])
    {
        if (in_DIAM[to] || to == p)
            continue;
        maxs.add(max(dp[to].diam, dp[to].farthest + 1), to);
        kek.add(dp[to].farthest + 1, to);
    }
    for (auto to : g[v])
    {
        if (in_DIAM[to] || to == p)
            continue;
        int kk = k;
        kk = max(kk, maxs.get({to}));
        kk = max(kk, kek.get({to}, 2));
        calc_self(to, v, kk);
        sz[v] += sz[to];
    }
}
void calc_left(int v, int p, int k)
{
    left_val[v] = max(self_val[v], k);
    for (auto to : g[v])
    {
        if (in_DIAM[to] || to == p)
            continue;
        calc_left(to, v, k);
    }
}
 
void calc_right(int v, int p, int k)
{
    right_val[v] = max(self_val[v], k);
    for (auto to : g[v])
    {
        if (in_DIAM[to] || to == p)
            continue;
        calc_right(to, v, k);
    }
}
vector<ll> solve(int _n, vector<pii> edges, vector<pii> queries)
{
    n = _n;
    for (auto edge : edges)
    {
        int v = edge.f;
        int u = edge.s;
        g[v].pb(u);
        g[u].pb(v);
    }
    A = get_farthest(1, 1);
    B = get_farthest(A, A);
    for (int v = B; v != A; v = parent[v])
        DIAM.pb(v);
    DIAM.pb(A);
    for (int i = 0; i < DIAM.size(); i++)
    {
        int v = DIAM[i];
        in_DIAM[v] = 1;
        in_DIAM_pos[v] = i;
    }
 
    for (int i = 0; i < DIAM.size(); i++)
    {
        int v = DIAM[i];
        dfs(v, v);
        calc_self(v, v);
    }
    for (int i = 0, farthest = 0; i < DIAM.size(); i++)
    {
        int v = DIAM[i];
        int prev = 0;
        left_val[v] = max(left_val[v], self_val[v]);
        if (i)
        {
            prev = left_val[DIAM[i - 1]];
            farthest = farthest + 1;
            left_val[v] = max(left_val[v], prev);
            left_val[v] = max(left_val[v], farthest + dp[v].farthest);
        }
        k_max maxs = k_max(2);
        for (auto to : g[v])
        {
            if (in_DIAM[to])
                continue;
            maxs.add(dp[to].farthest + 1, to);
        }
        for (auto to : g[v])
        {
            if (in_DIAM[to])
                continue;
            calc_left(to, v, max(prev, farthest + maxs.get({to})));
        }
        farthest = max(farthest, dp[v].farthest);
    }
 
    for (int i = DIAM.size() - 1, farthest = 0; i >= 0; i--)
    {
        int v = DIAM[i];
        int prev = 0;
        right_val[v] = max(right_val[v], self_val[v]);
        if (i + 1 < DIAM.size())
        {
            prev = right_val[DIAM[i + 1]];
            farthest = farthest + 1;
            right_val[v] = max(right_val[v], prev);
            right_val[v] = max(right_val[v], farthest + dp[v].farthest);
        }
        k_max maxs = k_max(2);
        for (auto to : g[v])
        {
            if (in_DIAM[to])
                continue;
            maxs.add(dp[to].farthest + 1, to);
        }
        for (auto to : g[v])
        {
            if (in_DIAM[to])
                continue;
            calc_right(to, v, max(prev, farthest + maxs.get({to})));
        }
        farthest = max(farthest, dp[v].farthest);
    }
 
    fen lefts, rights;
    for (int i = 1; i <= n; i++)
    {
        int pos = in_DIAM_pos[diam_parent[i]];
        lefts.inc(pos, 1);
        rights.inc(pos, 1);
        events[m++] = {left_val[i], {0, i}};
        events[m++] = {right_val[i], {1, i}};
    }
    for (int i = 0; i < DIAM.size(); i++)
    {
        int v = DIAM[i];
        events[m++] = {self_val[v], {2, v}};
    }
    sort(events, events + m);
    reverse(events, events + m);
 
    set<int> blocked;
    blocked.insert(0);
    blocked.insert(DIAM.size() - 1);
 
    for (int i = 0; i < m; i++)
    {
        int val = events[i].f;
        int type = events[i].s.f;
        int pos = in_DIAM_pos[diam_parent[events[i].s.s]];
        if (type == 0)
        {
            int l = pos + 1;
            int r = (*blocked.upper_bound(pos));
            ans[val] += rights.get(l, r);
            lefts.inc(pos, -1);
        }
        if (type == 1)
        {
            int l = (*(--blocked.lower_bound(pos)));
            int r = pos - 1;
            ans[val] += lefts.get(l, r);
            rights.inc(pos, -1);
        }
        if (type == 2)
        {
            int l = (*(--blocked.lower_bound(pos)));
            int r = (*blocked.upper_bound(pos));
            ans[val] += lefts.get(l, pos - 1) * rights.get(pos + 1, r);
            blocked.insert(pos);
        }
    }
    for (auto v : DIAM)
        ans[DIAM.size() - 1] += 1ll * sz[v] * (sz[v] - 1) / 2;
 
    k_max selfs = k_max(3);
    for (auto v : DIAM)
        selfs.add(self_val[v], v);
 
    vector<ll> result;
 
    for (auto query : queries)
    {
        if (query.f > 0)
        {
            int v = query.f;
            int u = query.s;
            int val = 0;
            if (diam_parent[v] == diam_parent[u])
                val = max(val, (int)DIAM.size() - 1);
            if (in_DIAM_pos[diam_parent[v]] > in_DIAM_pos[diam_parent[u]])
                swap(v, u);
            val = max(val, left_val[v]);
            val = max(val, right_val[u]);
            val = max(val, selfs.get({diam_parent[u], diam_parent[v]}));
            result.pb(val);
        }
        else
        {
            int k = query.s;
            result.pb(ans[k]);
        }
    }
    return result;
}
int main()
{
    int n, m;
    vector<pii> edges;
    vector<pii> queries;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        edges.pb({v, u});
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int type;
        scanf("%d", &type);
        if (type == 1)
        {
            int v, u;
            scanf("%d%d", &v, &u);
            queries.pb({v, u});
        }
        else
        {
            int k;
            scanf("%lld", &k);
            queries.pb({0, k});
        }
    }
    vector<ll> ans = solve(n, edges, queries);
    for (auto val : ans)
        printf("%lld\n", val);
    return 0;
}
Editor is loading...