这个题其实并没有做法显然

首先我们把操作抽象为3种

1 .查询路径上的第k大值

2 .删除某个节点的某个权值

3 .给某个节点添加一个权值

那么骑士搬家和武力值修正就统一了

那么非常自然的我们就可以想到用树链剖分+线段树来维护,线段树的每个节点存的就是相应区间的前k大值(前k个,即每个节点开一个数组).至于原图上的每个节点有多个权值怎么处理呢?非常简单,我们对于每个节点一个multiset就可以解决了

下面直接贴代码,应该不是很难懂,变量名应该还是蛮清晰的

#include <bits/stdc++.h>
#define LS tree[rt].son[0]
#define RS tree[rt].son[1]
using namespace std;

const int N=1e5+5;

int n,m,root,q,k;

int power[N];
multiset<int,greater<int> > s[N];
multiset<int>::iterator it;

struct Tree {
	int rank[25];
	int son[2];
} tree[N*20];
int tot;

bool cmp(int a,int b) {
	return a>b;
}

void push_up(int rt) {
	tree[rt].rank[0]=0;
	int j=1;
	for(int i=1; i<=tree[RS].rank[0]; i++) {
		for(; j<=tree[LS].rank[0]&&tree[LS].rank[j]>tree[RS].rank[i]; j++) {
			tree[rt].rank[++tree[rt].rank[0]]=tree[LS].rank[j];
			if(tree[rt].rank[0]>=k) return;
		}
		tree[rt].rank[++tree[rt].rank[0]]=tree[RS].rank[i];
		if(tree[rt].rank[0]>=k) return;
	}
	for(; j<=tree[LS].rank[0]; j++) {
		tree[rt].rank[++tree[rt].rank[0]]=tree[LS].rank[j];
		if(tree[rt].rank[0]>=k) return;
	}
	return;
}

void build(int &rt,int l,int r) {
	if(!rt) rt=++tot;
	if(l>=r) {
		for(it=s[l].begin(); it!=s[l].end(); it++) {
			tree[rt].rank[++tree[rt].rank[0]]=*it;
			if(tree[rt].rank[0]>=k) break;
		}
		return;
	}
	int mid=l+r>>1;
	build(LS,l,mid);
	build(RS,mid+1,r);
	push_up(rt);
}

void modify(int &rt,int l,int r,int pos,int val) {
	if(!rt) rt=++tot;
	if(l>=r) {
		tree[rt].rank[0]=0;
		if(val<0) {
			s[pos].erase(s[pos].find(-val));
		} else s[pos].insert(val);
		for(it=s[pos].begin(); it!=s[pos].end(); it++) {
			tree[rt].rank[++tree[rt].rank[0]]=*it;
			if(tree[rt].rank[0]>=k) break;
		}
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) modify(LS,l,mid,pos,val);
	else modify(RS,mid+1,r,pos,val);
	push_up(rt);
}

void query(int rt,int l,int r,int ll,int rr) {
	if(ll<=l&&rr>=r) {
		for(int i=1; i<=tree[rt].rank[0]; i++)
			power[++power[0]]=tree[rt].rank[i];
		return;
	}
	int mid=l+r>>1;
	if(ll<=mid) query(LS,l,mid,ll,rr);
	if(rr>mid) query(RS,mid+1,r,ll,rr);
}

struct Edge {
	int v,next;
} edge[N<<1];
int head[N],cnt;
void add(int u,int v) {
	edge[++cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

int deep[N],id[N],top[N],son[N],siz[N],parent[N],tim;

void dfs1(int u,int fa) {
	deep[u]=deep[fa]+1;
	parent[u]=fa;

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

void dfs2(int u,int tp) {
	id[u]=++tim;
	top[u]=tp;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u]; i; i=edge[i].next) {
		int v=edge[i].v;
		if(v==son[u]||deep[v]<deep[u]) continue;
		dfs2(v,v);
	}
}

void treequery(int x,int y) {
	power[0]=0;
	while(top[y]!=top[x]) {
		if(deep[top[y]]>deep[top[x]]) swap(x,y);
		query(root,1,n,id[top[x]],id[x]);
		x=parent[top[x]];
	}
	if(deep[y]>deep[x]) swap(x,y);
	query(root,1,n,id[y],id[x]);
	if(power[0]==0) {
		puts("-1");
		return ;
	}
	sort(power+1,power+power[0]+1,cmp);
	for(int i=1; i<=min(power[0],k); i++) printf("%d ",power[i]);
	puts("");
	return;
}

int loc[N],w[N];



int main() {
//	freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1,u,v; i<n; i++) {
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	scanf("%d",&m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&w[i],&loc[i]);
		s[id[loc[i]]].insert(w[i]);
	}
	scanf("%d%d",&q,&k);
	build(root,1,n);
	for(int i=1,t,x,y; i<=q; i++) {
		scanf("%d%d%d",&t,&x,&y);
		if(t==1) treequery(x,y);
		if(t==2) {
			modify(root,1,n,id[loc[x]],-w[x]);
			loc[x]=y;
			modify(root,1,n,id[loc[x]],w[x]);
		}
		if(t==3) {
			modify(root,1,n,id[loc[x]],-w[x]);
			w[x]=y;
			modify(root,1,n,id[loc[x]],w[x]);
		}
	}
	return 0;
}

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

这里我还脑补了另外一种做法,权当抛砖引玉因为我没有敲过,不知道能不能过

如果不带修的话我们的标准做法就是主席树上树,那带修怎么办呢?

我们可以想到带修主席树,即树状数组套权值线段树.那么如何将其迁移到树上呢?我们可以考虑dfn序.

考虑我们如果使用树状数组套权值线段树维护一段序列(就是大家平时做的动 态区间k小/大值),单点修改的影响就是该点以及其以后的所有权值线段树. 对于该题我们对于树上的每个节点维护一颗权值线段树,记录该节点到根节点的信息(就是树上主席树的做法).每个修改操作只会影响以该节点为根的子树的所有权值线段树的信息.那么与普通树状数组套权值线段树的区别就在这里.我们每次修改的影响只有子树,因为子树在dfn序上表现为一段连续的区间,那么我们也就能处理了.有兴趣的可以敲一敲,看一看