自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:18:00，当前版本为作者最后更新于2020-03-01 22:09:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门

感觉比 D 简单一点 （因为我对数论一窍不通）。

首先明确一点，选出的 $w_x$ 一定是第二大的，$w_y$ 一定是最大的，此时 $w_x\bmod w_y$ 最大。

• 为什么？不妨设 $w_x<w_y$，那么 $w_x\bmod w_y=w_x$，而 $w_y\bmod w_x$ 一定小于 $w_x$，所以选出的 $w_x,w_y$ 满足 $w_x<w_y$。

  因此，要使 $w_x\bmod w_y$ 最大，$w_x$ 一定是第二大的，$w_y$ 一定是最大的。

这样问题就被我们转化成了：

• 给定一条链，设 $x$ 为该链上权值严格第二大的节点，$y$ 为该链上权值最大的节点，求出 $w_x$。这可以用树剖和线段树维护。

• 求出去掉 $x,y$ 后剩余的点中严格第二大的权值。这可以用一个 multiset 维护。

其实，如果不带修，这道题目还能用主席树来做，可惜主席树无法支持这样的修改。

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
	int x=0,sign=0; char s=getchar();
	while(!isdigit(s))sign|=s=='-',s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
	return sign?-x:x;
}
const int N=1e5+5;
int ct,hd[N],nxt[N<<1],vv[N<<1];
inline void add(int u,int v){
	nxt[++ct]=hd[u],hd[u]=ct,vv[ct]=v;
}
int n,q,dnum,fa[N],dep[N],siz[N],son[N],ind[N],top[N],rk[N];
void dfs1(int id,int f,int d){
	fa[id]=f,siz[id]=1,dep[id]=d;
	for(int i=hd[id];i;i=nxt[i]){
		int to=vv[i];
		if(to!=f){
			dfs1(to,id,d+1);
			if(siz[son[id]]<siz[to])son[id]=to;
			siz[id]+=siz[to];
		}
	}
}
void dfs2(int id,int t){
	top[id]=t,ind[id]=++dnum,rk[dnum]=id;
	if(!son[id])return;
	dfs2(son[id],t);
	for(int i=hd[id];i;i=nxt[i]){
		int to=vv[i];
		if(to!=fa[id]&&to!=son[id])dfs2(to,to);
	}
}
multiset <int> s;
int val[N];
struct data{
	int fi,se;
}c[N<<2];
data mer(data a,data b){
	int fi=max(a.fi,b.fi);//维护最大/第二大值
	return {fi,max(a.fi==fi?a.se:a.fi,b.fi==fi?b.se:b.fi)}; 
}
void build(int l,int r,int x){
	if(l==r){
		c[x]={val[rk[l]],-1};
		return;
	}
	int m=l+r>>1;
	build(l,m,x<<1),build(m+1,r,x<<1|1);
	c[x]=mer(c[x<<1],c[x<<1|1]);
}
void modify(int l,int r,int x,int pos,int v){
	if(l==r){
		val[rk[l]]+=v;
		c[x]={val[rk[l]],-1};
		return;
	}
	int m=l+r>>1;
	if(pos<=m)modify(l,m,x<<1,pos,v);
	else modify(m+1,r,x<<1|1,pos,v);
	c[x]=mer(c[x<<1],c[x<<1|1]);
}
data query(int l,int r,int ql,int qr,int x){
	if(ql<=l&&r<=qr)return c[x];
	int m=l+r>>1; data ans={-1,-1};
	if(ql<=m)ans=mer(ans,query(l,m,ql,qr,x<<1));
	if(m<qr)ans=mer(ans,query(m+1,r,ql,qr,x<<1|1));
	return ans;
}
data query(int x,int y){
	data ans={-1,-1};
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=mer(ans,query(1,n,ind[top[x]],ind[x],1));
		x=fa[top[x]];
	}
	if(ind[x]>ind[y])swap(x,y);
	return mer(ans,query(1,n,ind[x],ind[y],1));
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs1(1,0,0),dfs2(1,1);
	for(int i=1;i<=n;i++)val[i]=read(),s.insert(val[i]);
	build(1,n,1);
	q=read();
	for(int i=0;i<q;i++){
		int op=read(),x=read(),y=read();
		if(op){
			data t=query(x,y);
			if(t.se==-1){
				puts("-1");
				continue;
			}
			printf("%d ",t.se);
			s.erase(s.find(t.fi)),s.erase(s.find(t.se));
			printf("%d\n",*(--s.lower_bound(*--s.end())));
			s.insert(t.fi),s.insert(t.se);
		}
		else{
			s.erase(s.find(val[x])),s.insert(val[x]+y);
			modify(1,n,1,ind[x],y);
		}
	}
	return 0;
}