HDU 4008. Parent and son

发表于 分类于

链接

http://acm.hdu.edu.cn/showproblem.php?pid=4008

题意

树上多次询问：以 $x$ 为树根，$y$ 的 $id$ 最小的儿子节点和子孙节点。

思路

以 $1$ 为树根对树重链剖分，然后我们可以将询问分成两种情况：

  1. $x$ 是 $y$ 的子孙节点

记 $1$ 为树根时 $x$ 到 $y$ 的路径上 $y$ 的儿子节点为 $z$，那么 $x$ 为树根时最小的儿子节点就是除 $z$ 外与 $y$ 相邻的最小节点，最小的子孙节点就是 $1$ 为树根时除 $z$ 的子树和 $y$ 外的最小节点。

  1. $x$ 不是 $y$ 的子孙节点

以 $x$ 为树根等价于以 $1$ 为树根。

我们可以用重链剖分求 $x,y$ 的 LCA 来判断是哪种情况。

注意：当 $x$ 是 $y$ 的子孙节点，求 LCA 时，最终跳到一条链时，两点可能重合，那么此时 $z$ 的 DFS 序就不是 $x$ 的 DFS 序加 $1$，因此还需记录节点 $y$ 上次的 top 值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n,m,cnt,sz[N],dfn[N],son[N],dep[N],fa[N],top[N],id[N],mn[N][2];
int w[N<<2],ls[N<<2],rs[N<<2];
VI g[N];
void init() {
    for(int i=1;i<=n;i++) {
        son[i]=0;
        mn[i][0]=mn[i][1]=INF;
        g[i].clear();
    }
    cnt=0;
}
void build(int p,int l,int r) {
    ls[p]=l,rs[p]=r;
    if(l==r) {
        w[p]=id[l];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    w[p]=min(w[p<<1],w[p<<1|1]);
}
int query(int p,int l,int r) {
    if(l>r) return INF;
    if(ls[p]>=l&&rs[p]<=r) return w[p];
    int mid=ls[p]+rs[p]>>1;
    if(r<=mid) return query(p<<1,l,r);
    if(l>mid) return query(p<<1|1,l,r);
    return min(query(p<<1,l,r),query(p<<1|1,l,r));
}
void dfs1(int u) {
    sz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(auto v:g[u]) if(v!=fa[u]) {
        fa[v]=u;
        mn[v][0]=u;
        if(v<mn[u][0]) mn[u][1]=mn[u][0],mn[u][0]=v;
        else if(v<mn[u][1]) mn[u][1]=v;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t) {
    top[u]=t;
    dfn[u]=++cnt;
    id[cnt]=u;
    if(son[u]) dfs2(son[u],t);
    for(auto v:g[u]) if(v!=fa[u]&&v!=son[u]) {
        dfs2(v,v);
    }
}
PII solve(int a,int b) {
    if(sz[a]==1) return MP(INF,INF);
    int t=a,tt;
    while(top[a]!=top[b]) {
        if(dep[top[a]]>dep[top[b]]) a=fa[top[a]];
        else {
            tt=dfn[top[b]];
            b=fa[top[b]];
        }
    }
    if(dep[a]<=dep[b]&&a==t) {
        int sn=a==b?id[tt]:id[dfn[a]+1];
        if(n-sz[sn]-1==0) return MP(INF,INF);
        PII ret;
        ret.FI=sn==mn[a][0]?mn[a][1]:mn[a][0];
        int l=a==b?tt:dfn[a]+1,r=l+sz[id[l]]-1;
        ret.SE=min({query(1,1,dfn[a]-1),query(1,dfn[a]+1,l-1),query(1,r+1,n)});
        return ret;
    }
    return MP(fa[t]==mn[t][0]?mn[t][1]:mn[t][0],query(1,dfn[t]+1,dfn[t]+sz[t]-1));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) {
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++) {
            int u,v;cin>>u>>v;
            g[u].PB(v),g[v].PB(u);
        }
        dfs1(1);dfs2(1,1);
        build(1,1,n);
        for(int i=1;i<=m;i++) {
            int rt,u;cin>>rt>>u;
            PII res=solve(u,rt);
            if(res.FI==INF) cout<<"no answers!"<<'\n';
            else cout<<res.FI<<' '<<res.SE<<'\n';
        }
        cout<<'\n';
    }
    return 0;
}