题解：P5478 [BJOI2015] 骑士的旅行

#include<bits/stdc++.h>
using namespace std;

char *p1,*p2,buf[100009];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline unsigned int read(){
    unsigned int x=0;
    char ch=nc();
    while(ch<48||ch>57){
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=(x << 3) + (x << 1) +ch-48,ch=nc();
    return x;
}

inline void out(unsigned int x) {
    if(x>9)out(x/10);
    putchar('0'+x%10);
}

#define N 40009
#define ls(i) (i<<1)
#define rs(i) ((i<<1)|1)
#define sp(i,j) i^=j,j^=i,i^=j
unsigned int n,m,q,k;
multiset<unsigned int> d[N];
vector<unsigned int> e[N];
unsigned int res, id[N], son[N], fa[N], h[N], top[N], sizee[N], rk[N], f[N], p[N];
struct V{
    multiset<unsigned int> d;
    unsigned int l, r;
    inline V operator+(const V &a) const {
        V c;
        c.l = l, c.r = a.r;
        int cnt = 0;
        for(auto it: a.d) {
        	cnt++;
        	if(cnt <= k) c.d.insert(it);
        	else break;
        }
        cnt = 0;
        for(auto it: d) {
        	cnt++;
        	if(cnt <= k) c.d.insert(it);
        	else break;
        }
        while(c.d.size() > k) c.d.erase(--c.d.end());
        return c;
    }
};
namespace xds{
    V tree[(N << 2) + 1];
    inline void build(const unsigned int &i, const unsigned int &l, const unsigned int &r) {
        tree[i].l = l, tree[i].r = r;
        if(l == r) {
            return;
        }
        const unsigned int mid = (l + r) >> 1;
        build(ls(i), l, mid),build(rs(i), mid + 1, r),tree[i] = tree[ls(i)] + tree[rs(i)];
    }
    inline void change(const unsigned int &i, const unsigned int &x) {
        if(tree[i].l == tree[i].r) {
            return;
        }
        const unsigned int mid = (tree[i].l + tree[i].r) >> 1;
        if(x <= mid) change(ls(i), x);
        else change(rs(i), x);
        tree[i] = tree[ls(i)] + tree[rs(i)];
    }
    inline V ask(const unsigned int &i, const unsigned int &l, const unsigned int &r) {
        if(l <= tree[i].l && tree[i].r <= r) return tree[i];
        const unsigned int mid = (tree[i].l + tree[i].r) >> 1;
        if(l <= mid && mid < r) return ask(ls(i), l, r) + ask(rs(i), l, r);
        if(l <= mid) return ask(ls(i), l, r);
        if(mid < r) return ask(rs(i), l, r);
    }
}
inline void dfs(const unsigned int &u,const unsigned int &faa,const unsigned int &hh) {
    h[u]=hh,fa[u]=faa,sizee[u]=1;
    unsigned cnt=0;
    for(auto to:e[u]) {
        if(to==faa) continue;
        dfs(to,u,hh+1);
        sizee[u]+=sizee[to];
        if(cnt <= sizee[to]) son[u]=to,cnt=sizee[to]; 
    }
}
inline void dfs2(const unsigned int &u,const unsigned int &topp) {
    top[u]=topp,id[u]=++res,rk[res]=u;
    if(!son[u]) return;
    dfs2(son[u],topp);
    for(auto to:e[u]) {
        if(to==fa[u]) continue;
        if(to==son[u]) continue;
        dfs2(to,to);
    }
}
inline void ask(unsigned int &x, unsigned int &y) {
    V ans;
    while(top[x] ^ top[y]) {
        if(h[top[x]] < h[top[y]]) sp(x, y);
        ans = ans + xds::ask(1, id[top[x]], id[x]);
        x = fa[top[x]];
    }
    if(id[x] > id[y]) sp(x, y);
    ans = ans + xds::ask(1, id[x], id[y]);
    if(!ans.d.size()) putchar('-'), putchar('1');
    else {
    	for(auto it: ans.d)
    		out(-it), putchar(' '); 
    }
    putchar('\n');
}
int ys[N];

inline void js(const unsigned int &i, const unsigned int &l, const unsigned int &r) {
    if(l == r) {
    	ys[l] = i;
        return;
    }
    const unsigned int mid = (l + r) >> 1;
    js(ls(i), l, mid),js(rs(i), mid + 1, r);
}
int main(){
    n = read();
    for(unsigned int i = 1, _u, _v; i < n; ++i) _u = read(), _v = read(), e[_u].push_back(_v), e[_v].push_back(_u);
    dfs(1, 0, 1), dfs2(1, 1);
    js(1, 1, n);
    m = read();
    for(unsigned int i = 1; i <= m; ++i) {
    	f[i] = read(), p[i] = read(), xds::tree[ys[id[p[i]]]].d.insert(-f[i]);
	}
    q = read(), k = read(), xds::build(1, 1, n);
    while(q--) {
        unsigned int op, x, y;
        op = read(), x = read(), y = read();
        if(op == 1) ask(x, y);
        if(op == 2) xds::tree[ys[id[p[x]]]].d.erase(xds::tree[ys[id[p[x]]]].d.find(-f[x])), xds::change(1, id[p[x]]), p[x] = y, xds::tree[ys[id[p[x]]]].d.insert(-f[x]), xds::change(1, id[p[x]]);
        if(op == 3) xds::tree[ys[id[p[x]]]].d.erase(xds::tree[ys[id[p[x]]]].d.find(-f[x])), f[x] = y, xds::tree[ys[id[p[x]]]].d.insert(-f[x]), xds::change(1, id[p[x]]);
    }
    return 0;
}