1. 题目

BZOJ 传送门=￣ω￣=

LuoGu 传送门=￣ω￣=

2. 题解

做了好久呀 QvQ

所以记录一下

考虑不带修改点权的树链第 K 大问题：

• 首先建主席树（权值线段树），其中 root[i]以 root[fa[i]]为基础上加入点 i 的点权，这样 root[i]所代表的权值线段树表示的是根节点到点 i 的树链。
• 对于点 a 和点 b，我们要求它们之间的路径上的第 K 大点权。设 a 与 b 的 lca 为 c，则我们在 root[a]+root[b]-root[c]-root[fa[c]]中二分就行了，和主席树求区间第 K 大是一个思路（这里不知道主席树求区间第 K 大的可以看看这个：【题解】K-th Number 主席树 POJ – 2104）

带修改点权操作也很好搞。

考虑修改点 a 的权值，把它的权值从 x 修改到了 y。

那么以 a 为根的子树内（包括 a）的每个点的主席树都要减去一个 x，加上一个 y。

看到子树，我们不难想到它们在 Dfs 序上是一段连续区间。

设 ld[a]为该子树内最小的 Dfs 序（也就是 a 的 Dfs 序），rd[a]为该子树内最大的 Dfs 序。

那我们要修改的主席树就是区间 $[ld[a],rd[a]]$内的那些。。。

这里可以看出是要实现 “区间修改，单点查询”。

用树状数组套上主席树即可。

所以我们这样搞：第 i 个点对应的主席树是第 ld[a]棵主席树。

然后修改的时候在树状数组里修改区间 $[ld[a],rd[a]]$内的主席树就行了。

好像还要离散化一下。

然后有个小优化，就是对于初始点权，不一定要当做 n 个修改来搞，可以直接按照无修改操作的那个方式建主席树，时空复杂度 $O(nlog_2n)$嘛。然后树状数组套主席树只用来维护修改量。

还有就是对于这题，理论上至少要开 $1062\times 80000$个节点的（如果全是修改操作而且每次修改在树状数组中都需要修改 $log_2n$个主席树），但是这样空间会爆炸，而且炸得不轻（大概要 972MB 的内存）。真不知道出题人这样搞想干啥。。。但实测只要开 $100\times 80000$个节点就够了（我最后还是开了 $175\times 80000$个节点）。如果要究其原因，大概是：

• 数据随机生成，修改操作较少（估计是 $50\%$的操作是修改吧）。
• 期望上面讲树状数组每次修改大概只有 $0.5log_2n$棵主席树被修改。

好吧真是玄学。

代码也很好懂，可以看看。

#include <bits/stdc++.h>

#define NS (80005)
#define LGS (17)
#define lowbit(a) (a&-a)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, t[NS], H[NS << 1], Hs, Q[NS][3];

vector<int> g[NS];

int pre[NS][LGS + 1], dep[NS], ld[NS], rd[NS], dfn;

void Dfs(int a, int fa)
{
    pre[a][0] = fa, dep[a] = dep[fa] + 1, ld[a] = ++dfn;
    for (int i = 1; i <= LGS; i += 1) pre[a][i] = pre[pre[a][i - 1]][i - 1];
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i], tmp != fa) Dfs(tmp, a);
    rd[a] = dfn;
}

int lca(int a, int b)
{
    if (dep[a] > dep[b]) swap(a, b);
    for (int i = LGS; i >= 0; i -= 1)
        if (dep[pre[b][i]] >= dep[a]) b = pre[b][i];
    if (a == b) return a;
    for (int i = LGS; i >= 0; i -= 1)
    if (pre[a][i] != pre[b][i])
        a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}

void Make_H()
{
    int top = Hs; sort(H + 1, H + 1 + Hs), H[0] = -1, Hs = 0;
    for (int i = 1; i <= top; i += 1) if (H[i] != H[i - 1]) H[++Hs] = H[i];
}

int Ht(int a)
{
    return lower_bound(H + 1, H + 1 + Hs, a) - H;
}

struct N {int d, l, r;} e[NS * 175];

int sz, rt[NS], dta[NS];

void Update(int pos, int d, int L, int R, int& x)
{
    e[++sz] = e[x], x = sz, e[x].d += d;
    if (L == R) return;
    int Mid = (L + R) >> 1;
    if (pos <= Mid) Update(pos, d, L, Mid, e[x].l);
    else Update(pos, d, Mid + 1, R, e[x].r);
}

void Build(int a)
{
    rt[a] = rt[pre[a][0]], Update(t[a], 1, 1, Hs, rt[a]);
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i], tmp != pre[a][0])
            Build(tmp);
}

void add(int x, int pos, int d)
{
    while (x <= n) Update(pos, d, 1, Hs, dta[x]), x += lowbit(x);
}

int Le[NS], Re[NS];

int Query(int k, int L, int R)
{
    if (L == R) return L;
    int Mid = (L + R) >> 1, sum = 0;
    for (int i = 1; i <= Le[0]; i += 1) sum -= e[e[Le[i]].r].d;
    for (int i = 1; i <= Re[0]; i += 1) sum += e[e[Re[i]].r].d;
    if (sum >= k)
    {
        for (int i = 1; i <= Le[0]; i += 1) Le[i] = e[Le[i]].r;
        for (int i = 1; i <= Re[0]; i += 1) Re[i] = e[Re[i]].r;
        return Query(k, Mid + 1, R);
    }
        for (int i = 1; i <= Le[0]; i += 1) Le[i] = e[Le[i]].l;
        for (int i = 1; i <= Re[0]; i += 1) Re[i] = e[Re[i]].l;
        return Query(k - sum, L, Mid);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1) IN(t[i]), H[++Hs] = t[i];
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g[a].push_back(b), g[b].push_back(a);
    for (int i = 1; i <= m; i += 1)
    {
        IN(Q[i][0]), IN(Q[i][1]), IN(Q[i][2]);
        if (!Q[i][0]) H[++Hs] = Q[i][2];
    }
    Dfs(1, 0), Make_H();
    for (int i = 1; i <= n; i += 1) t[i] = Ht(t[i]);
    Build(1);
    for (int i = 1, k, a, b, l; i <= m; i += 1)
    {
        k = Q[i][0], a = Q[i][1], b = Q[i][2];
        if (k)
        {
            l = lca(a, b);
            if (dep[a] + dep[b] - dep[l] - dep[l] + 1 < k)
            {
                puts("invalid request!");
                continue;
            }
            Le[0] = Re[0] = 0;
            Re[++Re[0]] = rt[a], Re[++Re[0]] = rt[b];
            Le[++Le[0]] = rt[l], Le[++Le[0]] = rt[pre[l][0]];
            for (int i = ld[a]; i; i -= lowbit(i)) Re[++Re[0]] = dta[i];
            for (int i = ld[b]; i; i -= lowbit(i)) Re[++Re[0]] = dta[i];
            for (int i = ld[l]; i; i -= lowbit(i)) Le[++Le[0]] = dta[i];
            for (int i = ld[pre[l][0]]; i; i -= lowbit(i)) Le[++Le[0]] = dta[i];
            printf("%d\n", H[Query(k, 1, Hs)]);
        }
        else
        {
            add(ld[a], t[a], -1), add(rd[a] + 1, t[a], 1), t[a] = Ht(b);
            add(ld[a], t[a], 1), add(rd[a] + 1, t[a], -1);
        }
    }
    return 0;
}