P10105 游戏

三点距离询问与树上三臂

问题

P10105 [GDKOI2023 提高组] 游戏
给定一棵 $n$ 个点的树，有 $Q$ 次询问。每次给出三条两两距离 $x,y,z$，要求构造三个点 $u,v,w$，使 $dis(u,v)=x$，$dis(u,w)=y$，$dis(v,w)=z$；保证每次询问有解。

数据规模：$1\le n,Q\le2\times10^5$，$0\le x,y,z\le2\times10^5$。

首先最基础的情况是 $u, v, w$ 三点在一条链上，此时三点可以直接塞在直径上，那问题就没有难度了。

不过还有一种情况是，三个点是同一个根的三个分支，设根到 $u, v, w$ 的距离分别为 $a, b, c$，那么可以得到 $a = (x + y - z) / 2,\ b = (x + z - y) / 2,\ c = (y + z - x) / 2$。

于是问题就转化为了，找一个中心点，使得它向三个方向延伸的最深距离 $d_{1} \ge a, d_{2} \ge b, d_{3} \ge c$。

于是我们维护每个节点的三个方向的最远可达深度，最后为了还原出具体的点位，我们还需要记录最远可达深度对应的那个点。

这个状态就可以用一个换根DP 来实现，先 DFS 收儿子方向的贡献，再换根补父亲方向的贡献。

接着考虑查询：对一个中心，把三条最大臂长降序记成 $(d_1,d_2,d_3)$；询问的 $(a,b,c)$ 也降序后，只需要找到一个中心满足 $d_{1} \ge a, d_{2} \ge b, d_{3} \ge c$。

这就是一个三维偏序问题，所以我们可以离线掉第一维，用树状数组下标来检索第二维，最后树状数组的值就可以维护第三维。

注：这里树状数组需要存的是 中心点 的编号，因为离线重新排序了数组，需要还原。

接着找到中心之后就按三个方向扩展即可，最后可能还有往上跳一部分距离，这个可以用类似倍增 LCA 的思想来实现。

复杂度为 $O((n+Q)\log n)$，空间复杂度为 $O(n\log n)$，其中倍增表占主要空间。

▶

P10105

const int maxn = 3e5 + 5;
const int maxlg = 20;

struct Dir {
    int len, son, far;
} dir[maxn][3];

vector<int> adj[maxn];
int up[maxn][maxlg], dep[maxn];

void add( int u, Dir cur ) {
    for( int j = 0; j < 3; ++ j ) {
        if( cur.len > dir[u][j].len ) {
            swap( cur, dir[u][j] );
        }
    }
}

void dfs1( int u, int p ) {
    up[u][0] = p, dep[u] = dep[p] + 1;
    for( int i = 1; i < maxlg; ++ i ) {
        int mid = up[u][i-1];
        up[u][i] = up[mid][i-1];
    }
    dir[u][0] = { 0, 0, u };
    dir[u][1] = { 0, 0, u };
    dir[u][2] = { 0, 0, u };
    for( int v : adj[u] ) {
        if( v == p ) continue;
        dfs1( v, u );
        add( u, { dir[v][0].len + 1, v, dir[v][0].far } );
    }
}

void dfs2( int u, int p ) {
    for( int v : adj[u] ) {
        if( v == p ) continue;
        int k = ( dir[u][0].son == v ? 1 : 0 );
        add( v, { dir[u][k].len + 1, u, dir[u][k].far } );
        dfs2( v, u );
    }
}

struct Node { 
    int val, pos; 
    bool operator < ( const Node oth ) const { return val > oth.val; }
};

struct State {
    int d1, d2, d3, id;
    bool operator < ( const State oth ) const { return d1 > oth.d1; }
} ps[maxn];

struct Query {
    Node A, B, C;
    int id;
    bool operator < ( const Query oth ) const { return A < oth.A; }
} qs[maxn];

struct BIT {
/* ================================================== */
Node tr[maxn];
int sz;
void init( int N ) { 
    sz = N + 1;
    fill( tr, tr + sz + 1, Node{ -1, 0 } );
}
void add( int idx, Node cur ) { idx ++;
    for( int i = idx; i; i -= i & -i ) {
        if( cur.val > tr[i].val ) tr[i] = cur;
    }
} // 单点修改
Node ask( int idx ) { idx ++;
    Node res = { -1, 0 };
    for( int i = idx; i <= sz; i += i & -i ) {
        if( tr[i].val > res.val ) res = tr[i];
    }
    return res;
} // 查询后缀最大值
/* ================================================== */
} bit;

int jump( int u, int k ) {
    for( int i = 0; i < maxlg; ++ i ) {
        if( ( k >> i ) & 1 ) u = up[u][i];
    }
    return u;
}

int get_lca( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    u = jump( u, dep[u] - dep[v] );
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( up[u][i] == up[v][i] ) continue;
        u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}

int movek( int u, int v, int k ) {
    int lca = get_lca( u, v );
    int du = dep[u] - dep[lca];
    int dv = dep[v] - dep[lca];
    if( k <= du ) return jump( u, k );
    else return jump( v, dv - ( k - du )  );
}

int ans[maxn][3];

void solve( ) {
    int n = read( );
    for( int i = 1; i < n; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    dfs1( 1, 0 );
    dfs2( 1, 0 );

    for( int i = 1; i <= n; ++ i ) {
        ps[i].d1 = dir[i][0].len;
        ps[i].d2 = dir[i][1].len;
        ps[i].d3 = dir[i][2].len;
        ps[i].id = i;
    }
    sort( ps + 1, ps + n + 1 );

    int Q = read( );
    for( int i = 1; i <= Q; ++ i ) {
        int x = read( ), y = read( ), z = read( );
        int a = ( x + y - z ) / 2;
        int b = ( x + z - y ) / 2;
        int c = ( y + z - x ) / 2;
        Node tmp[3] = { { a, 0 }, { b, 1 }, { c, 2 } };
        sort( tmp, tmp + 3 );
        qs[i] = { tmp[0], tmp[1], tmp[2], i };
    }
    sort( qs + 1, qs + Q + 1 );

    bit.init( n );
    int i = 1;
    for( int j = 1; j <= Q; ++ j ) {
        auto [A, B, C, idx] = qs[j];
        while( i <= n && ps[i].d1 >= A.val ) {
            bit.add( ps[i].d2, { ps[i].d3, ps[i].id });
            i ++;
        }
        Node res = bit.ask( B.val );
        int u = res.pos;
        Dir d1 = dir[u][0], d2 = dir[u][1], d3 = dir[u][2];
        ans[idx][A.pos] = movek( d1.far, u, d1.len - A.val );
        ans[idx][B.pos] = movek( d2.far, u, d2.len - B.val );
        ans[idx][C.pos] = movek( d3.far, u, d3.len - C.val );
    }

    for( int i = 1; i <= Q; ++ i ) {
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << '\n';
    }
}