結果

問題 No.2342 Triple Tree Query (Hard)
コンテスト
ユーザー vjudge1
提出日時 2026-01-10 20:55:38
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 810 ms / 10,000 ms
コード長 4,276 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,215 ms
コンパイル使用メモリ 222,796 KB
実行使用メモリ 148,644 KB
最終ジャッジ日時 2026-01-10 20:56:11
合計ジャッジ時間 21,038 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,mod=998244353;
int a[N],n,m,K,End[N];
int dfn[N],id[N],siz[N],cnt,son[N],dep[N],f[N],F[N][22],top[N],Top[N];
vector<int>e[N],Son[N],D[N];
struct Tree{
	int val,k,b;
}t[N<<2];
inline void update(int p,int k,int b){
	t[p].val=(t[p].val*k+b)%mod;
	t[p].k=t[p].k*k%mod;t[p].b=(t[p].b*k+b)%mod;
}
inline void pushdown(int p){
	if(t[p].k!=1||t[p].b!=0){
		update(p<<1,t[p].k,t[p].b);
		update(p<<1|1,t[p].k,t[p].b);
		t[p].k=1;t[p].b=0;
	}
}
inline void modify(int L,int R,int k,int b,int p=1,int l=1,int r=n){
	if(l>=L&&r<=R){update(p,k,b);return ;}
	int mid=(l+r)>>1;pushdown(p);
	if(mid>=L)modify(L,R,k,b,p<<1,l,mid);
	if(mid+1<=R)modify(L,R,k,b,p<<1|1,mid+1,r);
}
inline int query(int i,int p=1,int l=1,int r=n){
	if(l==r)return t[p].val;
	int mid=(l+r)>>1;pushdown(p);
	if(mid>=i)return query(i,p<<1,l,mid);
	else return query(i,p<<1|1,mid+1,r);
}
void build(int l,int r,int p){
	t[p].k=1;t[p].b=0;
	if(l==r){
		t[p].val=a[id[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);build(mid+1,r,p<<1|1);
}
int Get_f(int x){
	for(int i=20;i>=0;i--){
		if((K>>i)&1)x=F[x][i];
	}
	return f[x];
}
void dfs1(int a,int fa){
	siz[a]=1;f[a]=fa;dep[a]=dep[fa]+1;
	F[a][0]=fa;for(int i=1;i<=20;i++)F[a][i]=F[F[a][i-1]][i-1];
	for(int to:e[a]){
		if(to==fa)continue;
		dfs1(to,a);
		siz[a]+=siz[to];
		if(siz[to]>siz[son[a]])son[a]=to;
	}
}
struct nod{int l,r,i;}s1[N],s2[N];
vector<nod>z[N];
void dfs2(int a,int fa,int topp,int Topp,int Dep){
	if(Dep<=K+1)Topp=a;
	top[a]=topp;Top[a]=Topp;
	if(Dep>K)dfn[a]=++cnt,id[cnt]=a,End[topp]=cnt;
	else {
		if(Get_f(a)==0)D[dep[a]-1].push_back(a);
		Son[Get_f(a)].push_back(a);
	}
	if(son[a])dfs2(son[a],a,topp,Topp,Dep+1);
	for(int to:e[a]){
		if(to==fa||to==son[a])continue;
		dfs2(to,a,to,to,0);
	}
}
int v[N];
void dfs3(int a,int fa){
	if(v[a]){
		int o=Get_f(a);
		s2[o].l=min(s2[o].l,dfn[a]);s2[o].r=max(s2[o].r,dfn[a]);
	}
	else{
		int o=Get_f(a);
		s1[o].l=min(s1[o].l,dfn[a]);s1[o].r=max(s1[o].r,dfn[a]);
	}
	for(int x:Son[a]){dfn[x]=++cnt;id[cnt]=x;v[x]=1;}
	for(int to:e[a]){
		if(to==fa)continue;
		dfs3(to,a);
	}
	s1[fa].l=min(s1[fa].l,s1[a].l);s1[fa].r=max(s1[fa].r,s1[a].r);
	s2[fa].l=min(s2[fa].l,s2[a].l);s2[fa].r=max(s2[fa].r,s2[a].r);
}
void Modify1(int a,int k,int p,int q){
	while(a!=1){
		if(z[a][k].i)modify(dfn[z[a][k].i],dfn[z[a][k].i],p,q);
		if(z[a][k].l<=z[a][k].r)modify(z[a][k].l,z[a][k].r,p,q);
		k--;if(k<0)break;
		if(z[a][k].i)modify(dfn[z[a][k].i],dfn[z[a][k].i],p,q);
		if(z[a][k].l<=z[a][k].r)modify(z[a][k].l,z[a][k].r,p,q);
		a=f[a];
	}
	while(k>=0){
		if(z[a][k].i)modify(dfn[z[a][k].i],dfn[z[a][k].i],p,q);
		if(z[a][k].l<=z[a][k].r)modify(z[a][k].l,z[a][k].r,p,q);
		k--;
	}
}
void Modify2(int a,int p,int q){
	for(int i=0;i<=K;i++){
		if(z[a][i].i)modify(dfn[z[a][i].i],dfn[z[a][i].i],p,q);
		if(z[a][i].l<=z[a][i].r)modify(z[a][i].l,z[a][i].r,p,q);
	}
	if(s1[a].l<=s1[a].r)modify(s1[a].l,s1[a].r,p,q);
	if(s2[a].l<=s2[a].r)modify(s2[a].l,s2[a].r,p,q);
}
void Modify3(int s,int t,int p,int q){
	while(Top[s]!=Top[t]){
		if(dep[Top[s]]<dep[Top[t]])swap(s,t);
		modify(dfn[Top[s]],dfn[s],p,q);
		s=f[Top[s]];
	}
	if(dep[s]>dep[t])swap(s,t);
	modify(dfn[s],dfn[t],p,q);
}
bool cmp(int a,int b){return dep[a]<dep[b];}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>n>>m;K=10;
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs1(1,0);
	dfs2(1,0,1,1,0);
	for(int i=0;i<=K;i++){
		for(auto x:D[i])dfn[x]=++cnt,id[cnt]=x,v[x]=1;
	}
	for(int i=1;i<=n;i++)s1[i]=s2[i]={n+1,0,0};
	dfs3(1,0);
	for(int i=1;i<=n;i++){
		z[i].resize(K+1);
		for(int x=0;x<=K;x++)z[i][x]={n+1,0,0};
	}
	for(int i=1;i<=n;i++){
		int o=i,d=0;
		while(o&&d<=K){
			if(top[o]==top[i])z[o][d].i=i;
			else {
				z[o][d].l=min(z[o][d].l,dfn[i]);
				z[o][d].r=max(z[o][d].r,dfn[i]);
			}
			o=f[o];d++;
		}
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==1){
			int x;cin>>x;
			cout<<query(dfn[x])<<"\n";
		}
		if(op==2){
			int x,k,p,q;cin>>x>>k>>p>>q;
			Modify1(x,k,p,q);
		}
		if(op==3){
			int x,p,q;cin>>x>>p>>q;
			Modify2(x,p,q);
		}
		if(op==4){
			int s,t,p,q;cin>>s>>t>>p>>q;
			Modify3(s,t,p,q);
		}
	}
	return 0;
}
0