P3979 遥远的国度 树剖换根

传送门：https://www.luogu.com.cn/problem/P3979

题意

有一棵点数为n的树，每个点都有一个权值，（初始根不一定为1），接下来m个操作：

  • $1\;id$，将根修改为id
  • $2\;x\;y\;val$，将x到y的简单路径上所有点的权值修改为val
  • $3\;x$，在根为root下，询问以x为根的子树的最小值。

思路

虽然树根不一定为1，但是我们轻重链剖分，线段树维护序列，都按照以1为根来做。 操作二我们还是一样，线段树修改x到y的简单路径上的权值。$modify \_ chain(x,y,val)$。

关键是操作三，如果树根一直都是1的话，就是$query(1,dfn[x],dfn[x]+siz[x]-1)$

但是树根一直在变！！！所以这是一道树剖换根!

如果我们每次在换根的时候重新剖分，那复杂度会爆炸！所以不可能一直剖分。

先来观察树根和x的位置关系。

  • $root==x\;$答案就是[1,n]区间最小的值，即t[1].mn

  • $LCA(root,x)==x \;\&\&\; dep[root]>dep[x]$

这种情况要求x的子树中最小值，只需要去除LCA的儿子$LCA\_son$的子树区域，剩下的取最小即可。

$ans=min(query(1,1,dfn[LCA\_son]-1),query(1,dfn[LCA\_son]+siz[LCA\_son],n))$

  • else

x不是root的LCA，那么只需要查询x的子树即可。 $ans = query(1,dfn[x],dfn[x]+siz[x]-1)$

Code（85MS）

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

 const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

int root;
ll w[10000005];

/*--------------前向星建边---------------*/

const int MAXN = 1e6 + 10;

struct Edge {
    int v, next;
}e[MAXN << 1];

int head[MAXN << 1], cnt;

inline void add(int u, int v) {
    e[++cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

/*-------------轻重链剖分----------------*/

const int N = 1e6 + 10;

int siz[N], dep[N], fa[N], son[N];

void dfs1(int u, int par) {
    dep[u] = dep[fa[u] = par] + (siz[u] = 1);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == par) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u]  siz[v] > siz[son[u]])
            son[u] = v;
    }
}

int top[N], dfn[N], nodeof[N], tim;

void dfs2(int u, int topf) {
    nodeof[dfn[u] = ++tim] = u;
    top[u] = topf;
    if(!son[u]) return ;
    dfs2(son[u], topf);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u]  v == son[u]) continue;
        dfs2(v, v);
    }
}

/*------------线段树维护---------------*/

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2

struct Tree {
    int l, r;
    ll mn, tag;
}t[N << 2];

inline void push_up(int u) {
    t[u].mn = min(t[lc].mn, t[rc].mn);
}

inline void push_down(int u) {
    if(!t[u].tag) return ;
    t[lc].mn = t[u].tag;
    t[rc].mn = t[u].tag;
    t[lc].tag = t[u].tag;
    t[rc].tag = t[u].tag;
    t[u].tag = 0;
}

void build(int u, int l, int r) {
    t[u].l = l; t[u].r = r; t[u].tag = 0;
    if(l == r) {
        t[u].mn = w[nodeof[l]];
        return ;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    push_up(u);
}

void modify(int u, int ql, int qr, ll v) {
    if(ql <= t[u].l && t[u].r <= qr) {
        t[u].mn = v;
        t[u].tag = v;
        return ;
    }
    push_down(u);
    if(ql <= mid) modify(lc, ql, qr, v);
    if(qr > mid)  modify(rc, ql, qr, v);
    push_up(u);
}

ll query(int u, int ql, int qr) {
    if(ql <= t[u].l && t[u].r <= qr) return t[u].mn;
    push_down(u);
    ll ans = 1e18;
    if(ql <= mid) ans = min(ans, query(lc, ql, qr));
    if(qr > mid)  ans = min(ans, query(rc, ql, qr));
    return ans;
}

void modify_chain(int x, int y, ll v) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, dfn[top[x]], dfn[x], v);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, dfn[x], dfn[y], v);
}

/*-------------LCA---------------*/

int LCA_son; // 公共祖先儿子

int LCA(int x, int y) {
    LCA_son = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        if(fa[top[x]] == y) LCA_son = top[x];
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    if(!LCA_son) LCA_son = son[x];
    return x;
}

void solve() {

    int n, m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i < n; i++) {
        int u, v;
        scanf("%d%d",&u,&v);
        add(u, v);
        add(v, u);
    }

    for(int i = 1;i <= n; i++) {
        scanf("%lld",&w[i]);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    scanf("%d",&root);
    while(m--) {
        int opt; scanf("%d",&opt);
        if(opt == 1) {
            int id; scanf("%d",&id);
            root = id;
        }
        else if(opt == 2) {
            int x, y; ll v; scanf("%d%d%lld",&x,&y,&v);
            modify_chain(x, y, v);
        }
        else if(opt == 3) {
            int x; scanf("%d",&x);
            if(x == root)
                printf("%lld\n",t[1].mn);
            else if(LCA(x, root) == x && dep[root] > dep[x]) {
                if(dfn[LCA_son] + siz[LCA_son] <= n)
                    printf("%lld\n",min(query(1, 1, dfn[LCA_son] - 1), query(1, dfn[LCA_son] + siz[LCA_son], n)));
                else
                    printf("%lld\n",query(1, 1, dfn[LCA_son] - 1));
            }
            else
                printf("%lld\n",query(1, dfn[x], dfn[x] + siz[x] - 1));
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    int size=40<<20;
    __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/18/luogu-p3979/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！