Codeforces150E 题解

wzf2000
2019年8月7日

Codeforces150E 题解

题意：

• 求树上路径长度在$[L,R]$之间的中位数最大的路径（长度为偶数取后面（较大）那个）。

题解：

• 显然需要二分 $mid$，然后 $val \ge mid$ 的边赋值为 $1$，否则赋值为 $-1$。问题转化为树上是否存在路径长度在 $[L,R]$ 的路径路径和大于等于零。
• 这个可以树分治。每条路径都并定在某层的重心。所以考虑怎么求出 $rt$ 的不同子树中，是否存在两点满足要求。
• 第一想法是按某种顺序枚举子树，然后通过线段树维护深度确定的到 $rt$ 路径和最大值。然而这样是 $O(n \log^3 n)$ 的（然而我一开始没有意识到，斯波地撕烤了很久为什么T了）。
• 所以就有一种神奇方法：
  • 按从小到大（深度或者子树大小）枚举子树，然后每将一颗子树更新进到数组前，用双指针队列扫描。
  • 类似于启发式合并的方法，会发现这样是每步均摊 $O(1)$，所以总复杂度是 $O(n \log^2 n)$。

代码：

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define mid (l+r>>1)
#define N 100009
#define inf 0x3f3f3f3f
using namespace std;
int n, LL, RR, first[N], number = 1, sz[N], fa[N], Max[N];
int len, now_x, now_y, Ans_x, Ans_y, SZ[N], Ans = -1, deep[N];
vector<int> go[N];
struct edge
{
    int to, next, val, vis;
    void add(int x, int y, int z)
    {
        to = y, next = first[x], first[x] = number, val = z;
    }
    int v(int lim)
    {
        return val >= lim ? 1 : -1;
    }
}e[N << 1];
struct node
{
    int val, pos;
    node(int val = 0, int pos = 0) :val(val), pos(pos) {}
    bool operator <(const node &rhs) const
    {
        return val < rhs.val;
    }
    bool operator <=(const node &rhs) const
    {
        return val <= rhs.val;
    }
}Max_val[N << 2];
bool cmp(int x, int y)
{
    return SZ[e[x].to] < SZ[e[y].to];
}
node max(const node &A, const node &B)
{
    return A < B ? B : A;
}
int read()
{
    int x = 1;
    char ch;
    while (ch = gc, ch<'0' || ch>'9') if (ch == '-') x = -1;
    int s = ch - '0';
    while (ch = gc, ch >= '0'&&ch <= '9') s = s * 10 + ch - '0';
    return x*s;
}
void Get_G(int x, int y, int &G)
{
    sz[x] = 1, Max[x] = 0;
    for (int i = first[x]; i; i = e[i].next)
        if (!e[i].vis&&e[i].to != fa[x])
        {
            Get_G(e[i].to, y, G);
            sz[x] += sz[e[i].to];
            Max[x] = max(Max[x], sz[e[i].to]);
        }
    Max[x] = max(Max[x], y - sz[x]);
    if (Max[x] < Max[G]) G = x;
}
node Q[N << 1], q[N << 1];
int pos[N << 1];
void Dfs(int G, int y, int x, int last, int sum, int depth, int lim)
{
    q[depth] = max(q[depth], node(sum, x));
    if (depth >= LL&&depth <= RR&&sum >= 0)
    {
        now_x = x, now_y = G;
        return;
    }
    for (int i = first[x]; i; i = e[i].next)
        if (e[i].to != last && !e[i].vis)
        {
            Dfs(G, y, e[i].to, x, sum + e[i].v(lim), depth + 1, lim);
            if (now_x&&now_y) return;
        }
}
bool check(int G, int tmp, int y, int lim)
{
    for (int i = 1; i <= y; i++) Q[i] = node(-inf, 0);
    now_x = now_y = 0;
    for (int i = 0; i < go[G].size(); i++)
        if (!e[go[G][i]].vis)
        {
            int sz_now = 0;
            if (go[G][i] == tmp) sz_now = y - sz[G];
            else sz_now = sz[e[go[G][i]].to];
            for (int j = 1; j <= sz_now; j++) q[j] = node(-inf, 0);
            Dfs(G, y, e[go[G][i]].to, G, e[go[G][i]].v(lim), 1, lim);
            if (now_x&&now_y) return true;
            int head = 1, tail = 0, r = max(1, LL - sz_now);
            pos[tail] = 0;
            for (int j = sz_now; j; j--)
            {
                while (r + j <= RR&&node(-inf, 0) < Q[r]&&r <= y)
                {
                    while (head <= tail&&Q[pos[tail]] <= Q[r]) tail--;
                    pos[++tail] = r++;
                }
                while (head <= tail&&pos[head] + j < LL) head++;
                if (head <= tail&&Q[pos[head]].val + q[j].val >= 0&&pos[head] + j >= LL&&pos[head] + j <=RR)
                {
                    now_x = Q[pos[head]].pos;
                    now_y = q[j].pos;
                    return true;
                }
            }
            for (int j = 1; j <= sz_now; j++)
                Q[j] = max(Q[j], q[j]);
        }
    return false;
}
void solve(int x, int y)
{
    int G = 0;
    Get_G(x, y, G);
    int tmp = 0;
    for (int i = first[G]; i; i = e[i].next)
        if (e[i].to == fa[G]) tmp = i;
    int l = 0, r = inf, ret = 0, ret_x = 0, ret_y = 0;
    while (l<=r)
    {
        if (check(G, tmp, y, mid)) ret_x = now_x, ret_y = now_y, ret = mid, l = mid + 1;
        else r = mid - 1;
    }
    if (ret > Ans)
    {
        Ans = ret;
        Ans_x = ret_x;
        Ans_y = ret_y;
    }
    if (tmp && !e[tmp].vis)
    {
        e[tmp].vis = e[tmp ^ 1].vis = 1;
        solve(x, y - sz[G]);
    }
    for (int i = first[G]; i; i = e[i].next)
        if (!e[i].vis)
        {
            e[i].vis = e[i ^ 1].vis = 1;
            solve(e[i].to, sz[e[i].to]);
        }
}
void dfs(int x)
{
    SZ[x] = 1;
    deep[x] = deep[fa[x]] + 1;
    for (int i = first[x]; i; i = e[i].next)
    {
        if (e[i].to != fa[x]) fa[e[i].to] = x, dfs(e[i].to), SZ[x] += SZ[e[i].to];
        go[x].push_back(i);
    }
    int tmp = SZ[fa[x]];
    SZ[fa[x]] = n - SZ[x];
    sort(go[x].begin(), go[x].end(), cmp);
    SZ[fa[x]] = tmp;
}
int main()
{
    Max[0] = inf;
    n = read(), LL = read(), RR = read();
    for (int i = 1; i < n; i++)
    {
        int x = read(), y = read(), z = read();
        e[++number].add(x, y, z), e[++number].add(y, x, z);
    }
    dfs(1);
    solve(1, n);
    printf("%d %d\n", Ans_x, Ans_y);
    return 0;
}

 codeforces 点分治 题解