C++(g++ 7.5.0) 解法, 执行用时: 1298ms, 内存消耗: 210632K, 提交时间: 2023-02-17 21:13:55

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e6+5;
int n, m, q, dep[N], w[N], d[N], v[N], f[N][21], pos[N];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
	to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void dfs(int x,int fa) {
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	rep(i,1,20) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
	}
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;~i;--i) if(dep[y]<=dep[f[x][i]]) x=f[x][i];
	if(x==y) return x;
	for(int i=20;~i;--i) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
	return f[x][0];
}
void dfs2(int x,int fa) {
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==fa) continue;
		dfs2(y,x);
		d[x]+=d[y];
	}
}
signed main() {
	n=read(), m=read();
	rep(i,1,n) w[i]=read();
	rep(i,1,n-1) {
		int x=read(), y=read();
		add(x,y), add(y,x);
	}
	dfs(1,0);
	while(m--) {
		int op=read();
		if(op==1) {
			int x=read(), y=read(), k=read();
			int z=lca(x,y);
			d[x]+=k, d[y]+=k, d[z]-=k, d[f[z][0]]-=k;
		} else if(op==2) {
			++q;
			int x=read(), y=read();
			w[n+q]=x;
			dep[n+q]=dep[y]+1;
			add(n+q,y), add(y,n+q);
			f[n+q][0]=y;
			rep(i,1,20) f[n+q][i]=f[f[n+q][i-1]][i-1];
		} else {
			int x=read();
			v[x]=1;
		}
	}
	dfs2(1,0);
	rep(i,1,n+q) if(!v[i]) printf("%lld %lld\n",i,w[i]+d[i]);
}

C++(clang++11) 解法, 执行用时: 877ms, 内存消耗: 118156K, 提交时间: 2021-01-31 00:28:42

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5,T=19;
ll u[N],v[N];int f[N][T+1],d[N],n,m;
bool del[N];
struct edg{int to,nxt;}e[N<<1];int hd[N],cnt;
void add(int x,int y){
	e[++cnt]=(edg){y,hd[x]};hd[x]=cnt;
	e[++cnt]=(edg){x,hd[y]};hd[y]=cnt;
}
void dfs0(int x,int fa){
	d[x]=d[f[x][0]=fa]+1;for(int i=0;i<T;++i)f[x][i+1]=f[f[x][i]][i];
	for(int i=hd[x];i;i=e[i].nxt)if(e[i].to!=fa)dfs0(e[i].to,x);
}
int lca(int x,int y){
	if(d[x]>d[y])swap(x,y);
	for(int i=T;~i;--i)if(d[f[y][i]]>=d[x])y=f[y][i];
	if(x==y)return x;
	for(int i=T;~i;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
void dfs1(int x,int fa){
	for(int i=hd[x];i;i=e[i].nxt)if(e[i].to!=fa)
		dfs1(e[i].to,x),v[x]+=v[e[i].to];
}
struct lt{int op,x,y,k;}lst[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&u[i]);
	for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),add(x,y);
	for(int i=0;i<m;++i){
		scanf("%d",&lst[i].op);
		if(lst[i].op==1)scanf("%d%d%d",&lst[i].x,&lst[i].y,&lst[i].k);
		else if(lst[i].op==2)scanf("%d%d",&u[++n],&lst[i].y),add(n,lst[i].y);
		else scanf("%d",&lst[i].x),del[lst[i].x]=true;
	}
	dfs0(1,0);
	for(int i=0;i<m;++i)if(lst[i].op==1){
		int &x=lst[i].x,&y=lst[i].y,&k=lst[i].k;
		v[x]+=k;v[y]+=k;v[x=lca(x,y)]-=k;v[f[x][0]]-=k;
	}
	dfs1(1,1);
	for(int i=1;i<=n;++i)if(!del[i])printf("%d %lld\n",i,u[i]+v[i]);
	return 0;
}