#1181663 (C++17) No.2342 Triple Tree Query (Hard)

• 問題: No.2342 Triple Tree Query (Hard)
• ユーザー: vjudge1
• 提出日時: 2026-08-30 20:56:32
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 509 ms / 10,000 ms
• コード長: 3,240 bytes
• コンパイル時間: 1,424 ms
• コンパイル使用メモリ: 231,856 KB
• 実行使用メモリ: 99,412 KB
• 最終ジャッジ日時: 2026-08-30 20:56:56
• 合計ジャッジ時間: 17,308 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 36

ソースコード

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,K=10,P=998244353;
typedef vector<int> vi;
typedef vector<pair<int,int> > vii;
#define eb emplace_back
int n,m,va[N];
int sz[N],son[N],dp[N],seg[N],rev[N],fa[N],tp[N];
vi e[N],g[N];
vii sub[N],ks[N][K+1];
int t1[N<<2],t2[N<<2];
inline int md(int x){
	return x>=P?x-P:x;
}
#define L k<<1
#define R k<<1|1
void build(int k,int l,int r){
	t1[k]=1,t2[k]=0;
	if(l==r){
		t2[k]=va[rev[l]];
		return;
	}
	int mid=l+r>>1;
	build(L,l,mid),build(R,mid+1,r);
}
void pusht1(int k,int v){
	t2[k]=1ll*t2[k]*v%P,t1[k]=1ll*t1[k]*v%P;
}
void pusht2(int k,int v){
	t2[k]=md(t2[k]+v);
}
void pushdown(int k){
	if(t1[k]!=1){
		pusht1(L,t1[k]);
		pusht1(R,t1[k]);
		t1[k]=1;
	}
	if(t2[k]){
		pusht2(L,t2[k]);
		pusht2(R,t2[k]);
		t2[k]=0;
	}
}
void modify(int k,int l,int r,int x,int y,int c,int d){
	if(x<=l&&r<=y)return pusht1(k,c),pusht2(k,d);
	int mid=l+r>>1;
	pushdown(k);
	if(x<=mid)modify(L,l,mid,x,y,c,d);
	if(y>mid)modify(R,mid+1,r,x,y,c,d);
}
int ask(int k,int l,int r,int x){
	if(l==r)return t2[k];
	int mid=l+r>>1;
	pushdown(k);
	if(x<=mid)return ask(L,l,mid,x);
	else return ask(R,mid+1,r,x);
}
void upd(vii &a){
	vii b;
	sort(a.begin(),a.end());
	for(auto v:a){
		if(!b.empty()&&b.back().second+1==v.first)b.back().second=v.second;
		else b.eb(v);
	}
	a=b;
}
void dfs1(int x){
	sz[x]=1;
	for(auto v:e[x])if(!sz[v]){
		dp[v]=dp[x]+1,fa[v]=x;
		g[x].eb(v);
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]])son[x]=v;
	}
}
void dfs2(int x){
	vi s1,s2;
	for(int i=x;i;i=son[i])s1.eb(i),tp[i]=x;
	for(int i=0;i<=K;++i){
		for(auto v:s1){
			if(!seg[v])seg[v]=++seg[0],rev[seg[0]]=v;
			for(auto w:g[v])s2.eb(w);
		}
		s1=s2,s2.clear();
	}
	for(int i=x;i;i=son[i])for(auto v:g[i])if(v!=son[i])dfs2(v);
}
void dfs3(int x){
	sub[x].eb(seg[x],seg[x]),ks[x][0].eb(seg[x],seg[x]);
	for(auto v:g[x]){
		dfs3(v);
		for(auto w:sub[v])sub[x].eb(w);
		for(int i=0;i<K;++i)for(auto w:ks[v][i])ks[x][i+1].eb(w);
	}
	upd(sub[x]);
	for(int i=0;i<=K;++i)upd(ks[x][i]);
}
void Chg(vii &a,int c,int d){
	for(auto v:a)modify(1,1,n,v.first,v.second,c,d);
}
void Chg2(int x,int y,int c,int d){
	vii a;
	for(int j=y,nw=x;j>=-y;--j){
		if(fa[nw]&&dp[x]+dp[x]+j-2*dp[fa[nw]]<=y)nw=fa[nw];
		for(auto v:ks[nw][dp[x]+j-dp[nw]])a.eb(v);
	}
	upd(a);
	Chg(a,c,d);
}
void Chg3(int x,int c,int d){
	Chg(sub[x],c,d);
}
void getl(vii &a,int y,int x){
	int u=y;
	while(seg[u]+dp[x]-dp[u]!=seg[x])a.eb(seg[u],seg[u]),u=son[u];
	a.eb(seg[u],seg[x]);
}
void Chg4(int x,int y,int c,int d){
	vii a;
	for(int fx=tp[x],fy=tp[y];fx!=fy;x=fa[fx],fx=tp[x]){
		if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
		getl(a,fx,x);
	}
	if(dp[x]<dp[y])swap(x,y);
	getl(a,y,x);
	upd(a);
	Chg(a,c,d);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		e[x].push_back(y),e[y].push_back(x);
	}
	for(int i=1;i<=n;++i)scanf("%d",&va[i]);
	dfs1(1);dfs2(1);dfs3(1);
	build(1,1,n);
	for(int i=1,op,x,y,c,d;i<=m;++i){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&x);
			printf("%d\n",ask(1,1,n,seg[x]));
		}
		if(op==2){
			scanf("%d%d%d%d",&x,&y,&c,&d);
			Chg2(x,y,c,d);
		}
		if(op==3){
			scanf("%d%d%d",&x,&c,&d);
			Chg3(x,c,d);
		}
		if(op==4){
			scanf("%d%d%d%d",&x,&y,&c,&d);
			Chg4(x,y,c,d);
		}
	}
	return 0;
}