結果

問題 No.2342 Triple Tree Query (Hard)
コンテスト
ユーザー vjudge1
提出日時 2024-10-16 09:56:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,988 bytes
コンパイル時間 2,719 ms
コンパイル使用メモリ 210,412 KB
最終ジャッジ日時 2025-02-24 19:58:36
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other RE * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define mkp(x,y) make_pair(x,y)
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=1e5+10,M=12,mod=998244353;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Fun{
	int k,b;
	Fun(ll _k=1,ll _b=0){
		k=_k;
		b=_b;
	}
	inline void operator=(pi rhs){
		k=rhs.fi;
		b=rhs.se;
	}
	inline bool operator==(const pi&rhs)const{
		return k==rhs.fi&&b==rhs.se;
	}
	inline bool operator!=(const pi rhs)const{
		return !(*this==rhs);
	}
	inline friend Fun operator+(Fun A,Fun B){
		Fun ans;
		ans.k=1ll*A.k*B.k%mod;
		ans.b=(1ll*B.k*A.b%mod+B.b)%mod;
		return ans;
	}
	inline friend Fun operator+=(Fun &a,const Fun &b){
		return a=a+b;
	}
};
int c,n,q,op,x,y,k,b,r,cnt;
int a[N],z[N],t[N],fa[N],id[N],dep[N],siz[N],dfn[N];
vector<int> E[N];
class Tree{
public:
	struct Node{
		int l,r;
		int Min;
		Fun tag[M];
	}X[N<<2];
	inline void build(int k,int l,int r){
		X[k].l=l,X[k].r=r;
		if(l==r){
			X[k].Min=dep[id[l]];
			X[k].tag[0]=mkp(0,a[id[l]]);
			return ;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		X[k].Min=min(X[k<<1].Min,X[k<<1|1].Min);
	}
	inline void add(int k,int d,Fun v){
		if(d<X[k].Min)
		  return ;
		X[k].tag[d-X[k].Min]+=v;
	}
	inline void push_down(int k){
		For(i,0,10){
		    if(X[k].tag[i]!=mkp(1,0)){
		    	add(k<<1,X[k].Min+i,X[k].tag[i]);
		    	add(k<<1|1,X[k].Min+i,X[k].tag[i]);
		    	X[k].tag[i]=Fun();
			}
		}
		if(X[k].tag[11]!=mkp(1,0)){
			ll x=max(0,X[k].Min+11-X[k<<1].Min);
			For(i,x,M-1)
			  X[k<<1].tag[i]+=X[k].tag[11];
			x=max(0,X[k].Min+11-X[k<<1|1].Min);
			For(i,x,M-1)
			  X[k<<1|1].tag[i]+=X[k].tag[11];
			 X[k].tag[11]=Fun();			
		}
	}
	inline void update(int k,int l,int r,int d,Fun v){
		if(X[k].l==l&&r==X[k].r){
			if(d==-1){
				For(i,0,M-1)
				  X[k].tag[i]=X[k].tag[i]+v;
			}
			else
			  add(k,d,v);
			return ;
		}
		push_down(k);
		int mid=(X[k].l+X[k].r)>>1;
		if(r<=mid)
		  update(k<<1,l,r,d,v);
		else if(l>mid)
		  update(k<<1|1,l,r,d,v);
		else{
			update(k<<1,l,mid,d,v);
			update(k<<1|1,mid+1,r,d,v);
		}
	}
	inline int query(int k,int i){
		if(X[k].l==i&&i==X[k].r)
		  return X[k].tag[0].b;
		push_down(k);
		ll mid=(X[k].l+X[k].r)>>1;
		if(i<=mid)
		  return query(k<<1,i);
		else
		  return query(k<<1|1,i); 
	}
}T;
inline void add(int u,int v){
	E[u].push_back(v);
	E[v].push_back(u);
}
inline void dfs1(int u,int f){
	siz[u]=1;
	for(auto v:E[u]){
		if(v==f)
		  continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[z[u]])
		  z[u]=v;
	}
}
inline void dfs2(int u,int k){
	dfn[u]=++cnt;
	id[cnt]=u;
	t[u]=k;
	if(!z[u])
	  return ;
	dfs2(z[u],k);
	for(auto v:E[u]){
		if(v==fa[u]||v==z[u])
		  continue;
		dfs2(v,v);
	}
}
inline void update(int x,int y,Fun v){
	while(t[x]!=t[y]){
		if(dep[t[x]]<dep[t[y]])
		  swap(x,y);
		//cerr<<x<<' '<<y<<'\n';
		T.update(1,dfn[t[x]],dfn[x],-1,v);
		x=fa[t[x]];
	}
	if(dep[x]>dep[y])
	  swap(x,y);
	T.update(1,dfn[x],dfn[y],-1,v);
}
//inline void dfs(ll u,ll fa,ll r,Fun t){
//	T.update(1,dfn[u],dfn[u],t);
//	if(!r)
//	  return ;
//	for(auto v:E[u]){
//		if(v==fa)
//		  continue;
//		dfs(v,u,r-1,t);
//	}
//}
void get(int x,int y,int k,int b){
	while(x&&y>=0){
		if(fa[x]&&y>1){
			T.update(1,dfn[x],dfn[x]+siz[x]-1,dep[x]+y,{k,b});
			T.update(1,dfn[x],dfn[x]+siz[x]-1,dep[x]+y-1,{k,b});
//			tag[k][x]=(tag[k][x]+b)%mod;
//			tag[k-1][x]=(tag[k-1][x]+b)%mod;	
		}
		else{
			For(i,0,y)
			  T.update(1,dfn[x],dfn[x]+siz[x]-1,dep[x]+i,{k,b});
//			  tag[i][x]=(tag[i][x]+b)%mod;
		}
		x=fa[x];
		y--;
	}
}
int main(){
//	open("A.in","A.out");
	n=read(),q=read();
	For(i,1,n-1)
	  add(read(),read());
	For(i,1,n)
	  a[i]=read();
	dfs1(1,1);
	dfs2(1,1);
	T.build(1,1,n);
//	For(i,1,n){
//		//cerr<<i<<"->"<<dfn[i]<<'\n';
//	}
	while(q--){
		op=read(),x=read();
		//cerr<<"Yes"<<' '<<op<<'\n';;
		if(op==1){
			write(T.query(1,dfn[x]));
			putchar('\n');
		}
		else if(op==2){
			y=read(),k=read(),b=read();
			update(x,y,{k,b});
		}
		else if(op==3){
			k=read(),b=read();
			T.update(1,dfn[x],dfn[x]+siz[x]-1,-1,{k,b});
		}
		else{
			r=read(),k=read(),b=read();
//			if(c==6)
			  get(x,r,k,b);
//			else
//			  dfs(x,0,r,{k,b});
		}
	}
	return 0;
}
0