我哪来的自信…

懵逼的 题目

扯淡的 题解

什么时候讲过的来着…

LCT据说没办法搞子树(贼废, 那就树链剖分吧

我们发现换根是唬人的…对于查询的点$x$
$$
\mathrm{return}\,\,\min \begin{cases}
[x.begin, x.end]\,\,\, newroot = an\,\, ancestor\,\, of\,\,x \\
[1, y.begin - 1]\cup[y.end + 1, n]\,\,\,y\,\,is\,\,a\,\,ancestor\,\,of\,\,newroot\cap fa[y] = x\\
[1, n]\,\,\,x=newroot
\end{cases}
$$
那么现在的问题就转化为了怎么找一个节点$newroot$在另一个节点$x$的哪个子树中, 枚举肯定不行…菊花图就卡炸了..

考虑$LCA$的过程, 最后一步找的是$LCA$的两个儿子(也就是在哪一棵子树中), 那么我们用$LCA$的过程, 就可以找到$newroot$在$x$的哪一棵子树中了…

又: 我一直以为…我写的非常高明不用判断最后一个条件来着…然后发现写残了…调了三节课…重构了两遍…

又又: 仔细想一想$deep$小的是靠上的节点不要晕了…

沙茶的 代码

/**************************************************************
    Problem: 3083
    User: Cansult
    Language: C++
    Result: Accepted
    Time:5164 ms
    Memory:35596 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define MAXL (20 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
const int root = 1;
int dqroot;
using namespace std;
struct tnode
{
    int deep, d[MAXL], top, hs, zh, size, begin, end;
}ta[MAXN];
int a[MAXN], cnta, n, lgn;
struct tedg
{
    int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntb = -1;
struct node
{
    int le, ri, zh, lazy;
}b[MAXN << 3];
void push_up(int dq)
{ b[dq].zh = min(b[LS(dq)].zh, b[RS(dq)].zh); }
void push_down(int dq)
{
    int& x = b[dq].lazy;
    b[LS(dq)].zh = b[RS(dq)].zh = x;
    b[LS(dq)].lazy = b[RS(dq)].lazy = x;
    x = 0;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].lazy = 0;
    if (le == ri)
    {
        b[dq].zh = a[le];
        return ;
    }
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
    push_up(dq);
}
void xg(int dq, int le, int ri, int zh)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy = b[dq].zh = zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy)
        push_down(dq);
    if (le > mi)
        xg(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    push_up(dq);
}
int cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy)
        push_down(dq);
    if (le > mi)
        return cx(RS(dq), le, ri);
    else if (ri <= mi)
        return cx(LS(dq), le, ri);
    else
        return min(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].size = 1;
    ta[dq].hs = 0;
    for (int i = 1; i <= lgn; i++)
        ta[dq].d[i] = ta[ta[dq].d[i - 1]].d[i - 1];
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].d[0])
        {
            ta[tb[i].to].d[0] = dq;
            init(tb[i].to, deep + 1);
            ta[dq].size += ta[tb[i].to].size;
            if (ta[tb[i].to].size > ta[ta[dq].hs].size)
                ta[dq].hs = tb[i].to;
        }
}
void dfs(int dq)
{
    a[ta[dq].begin = ++cnta] = ta[dq].zh;
    if (ta[dq].hs)
        ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].d[0] && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    ta[dq].end = cnta;
}
void solve(int x, int y, int zh)
{
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
            swap(x, y);
        xg(1, ta[ta[x].top].begin, ta[x].begin, zh);
        x = ta[ta[x].top].d[0];
    }
    if (ta[x].deep > ta[y].deep)
        swap(x, y);
    xg(1, ta[x].begin, ta[y].begin, zh);
}
int findson(const int x)
{
    int y = dqroot;
    for (int i = lgn; i >= 0; i--)
        if (ta[ta[y].d[i]].deep > ta[x].deep) // 这玩意是大于...
            y = ta[y].d[i];
    return (ta[y].d[0] == x ? y : root);
}
int solve(int x)
{
    if (x == dqroot) // 本来以为可以不加这个来着...艹
        return cx(1, 1, n);
    int y = findson(x);
    if (ta[y].deep <= ta[x].deep)
        return cx(1, ta[x].begin, ta[x].end);
    int re = INF;
    if (ta[y].begin > 1)
        re = min(re, cx(1, 1, ta[y].begin - 1));
    if (ta[y].end < n)
        re = min(re, cx(1, ta[y].end + 1, n));
    return re;
}
void adn(int from, int to)
{
    tb[++cntb].next = tg[from];
    tb[cntb].from = from;
    tb[cntb].to = to;
    tg[from] = cntb;
}
int lg(int x)
{
    int re = 0;
    for (; (1 << re) <= x; re++)
        continue;
    return re;
}
int main()
{
//    cout << "Hello world!" << endl;
    memset(tg, -1, sizeof(tg));
    int q;
    scanf("%d%d", &n, &q);
    lgn = lg(n); // ...
    for (int i = 1; i < n; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &ta[i].zh);
    ta[root].d[0] = root, ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    scanf("%d", &dqroot);
    for (int i = 1; i <= q; i++)
    {
        int sre, srx, sry, srz;
        scanf("%d", &sre);
        if (sre == 1)
            scanf("%d", &dqroot);
        else if (sre == 2)
            scanf("%d%d%d", &srx, &sry, &srz), solve(srx, sry, srz);
        else
            scanf("%d", &srx), printf("%d\n", solve(srx));
    }
    return 0;
}

/*
3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
*/

By sb Cansult