結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー vjudge1vjudge1
提出日時 2024-10-15 15:05:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 5,868 bytes
コンパイル時間 1,847 ms
コンパイル使用メモリ 174,412 KB
実行使用メモリ 814,532 KB
最終ジャッジ日時 2024-10-15 15:05:31
合計ジャッジ時間 11,031 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define F(i,x,y) for (int i=(x);i<=(y);i++)
#define R(i,x,y) for (int i=(x);i>=(y);i--)
#define p2i pair<int,int>
#define ll long long
#define fi first
#define se second
#define MT int testcases;cin>>testcases;while(testcases--)
#define pub push_back
#define ins insert
#define puf push_front
#define vec vector
#define umap unordered_map
#define uset unordered_set
#define popf pop_front
#define popb pop_back
#define NOI2024 GG
#define m1i modint<998244353>
#define m2i modint<1000000007>
#define iosoptim ios::sync_with_stdio(0);cin.tie(0);
#define uselessline cout.tie(0);
using namespace std;
namespace melodyextras{

	namespace fastio{const int BUFSIZE=1048576;char ibuf[BUFSIZE],obuf[BUFSIZE];int itop=0,iptr=0,optr=0;
	char getchar(){while(iptr>=itop){itop=fread(ibuf,1,BUFSIZE,stdin);iptr=0;}return ibuf[iptr++];
	}void flush(){fwrite(obuf,1,optr,stdout);optr=0;}void putchar(char c){obuf[optr++]=c;if(optr==BUFSIZE)flush();}}
	namespace iowhl {
		int read () {
			int a = 0, x = 0;
			char c = fastio::getchar();
			while (!isdigit(c)) a = (c == '-' ? 1 : a), c = fastio::getchar();
			while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = fastio::getchar();
			return a ? -x : x;
		}
		void write (int x) {
			if (x < 0) x = -x, fastio::putchar('-');
			if (x > 9) write (x / 10);
			fastio::putchar (x % 10 + 48);
		}
	}

	template<int m> struct modint{
		int val;
		modint(){val=0;}
		modint(int x) {val=x%m;}
		modint(long long x) {val=x%m;}
		modint(const modint &obj) {val=obj.val;}
		modint operator +(modint b) const {return {(val+b.val)%m};}
		modint operator -(modint b) const {return {(val+m-b.val)%m};}
		modint operator -() const {return {val?m-val:0};}
		modint operator *(modint b) const {return {1ll*val*b.val%m};}
		modint inversion() const {
			int a=1,u=val,k=m-2;
			while(k){
				if(k&1)a=1ll*a*u%m;
				u=1ll*u*u%m;
				k>>=1;
			}
			return {a};
		}
		modint operator /(modint b) const {return operator *(b.inversion());}
		modint operator +=(modint b) {return (*this)=(*this)+b;}
		modint operator -=(modint b) {return (*this)=(*this)-b;}
		modint operator *=(modint b) {return (*this)=(*this)*b;}
		modint operator /=(modint b) {return (*this)=(*this)/b;}
	};
	template<int m> istream& operator >>(istream &in,modint<m> &x) {
		return in>>x.val;
	}
	template<int m> ostream& operator <<(ostream &out,modint<m> x) {
		return out<<x.val;
	}
	template<int m> modint<m> qpow(modint<m> x,int k){
		modint<m> a=1,u=x;
		while(k){
			if(k&1)a=a*u;
			u=u*u;
			k>>=1;
		}
		return a;
	}
	template<typename T> T popc(int x){return __builtin_popcount(x);}
}
using namespace melodyextras;

const int N=1e5+5;
int sub,n,q;
m1i a[N];
vector<int> g[N];
int top[N],dfn[N],sz[N],hson[N],rd[N],tick,fa[N],dep[N];
namespace st{
	int ls[2*N],rs[2*N],ld[2*N];
	struct mat{
		m1i k,b;
		mat () {
			k=1;
			b=0;
		}
		mat (m1i k,m1i b):k(k),b(b){
			
		}
		mat operator *(mat y)const {
			return mat(k*y.k,b*y.k+y.b);
		}
	};
	const mat I;
	mat tag[2*N][11],all[2*N];
	void simp(int p,mat x,int d){
		if(d==0){
			all[p]=all[p]*x;
		}
		else if (d==-1){
			all[p]=all[p]*x;
			F(i,0,10)tag[p][i]=tag[p][i]*x;
		}
		else {
			if(d>=ld[p]&&d<=ld[p]+10)tag[p][d-ld[p]]=tag[p][d-ld[p]]*x;
		}
	}
	void pushdown(int p){
		F(i,0,10){
			simp(ls[p],tag[p][i],i+ld[p]);
			simp(rs[p],tag[p][i],i+ld[p]);
			tag[p][i]=I;
		}
		F(i,0,10){
			if(ld[ls[p]]+i>ld[p]+10) simp(ls[p],all[p],i+ld[ls[p]]);
			if(ld[rs[p]]+i>ld[p]+10) simp(rs[p],all[p],i+ld[rs[p]]);
		}
		simp(ls[p],all[p],0);
		simp(rs[p],all[p],0);
		all[p]=I;
	}
	void modify(int p,int tl,int tr,int ml,int mr,int dl,int dr,mat x){
		if(ml<=tl&&tr<=mr){
			F(d,dl,dr) simp(p,x,d);
		}
		else {
			pushdown(p);
			int mid=(tl+tr)>>1;
			if(ml<=mid)modify(ls[p],tl,mid,ml,mr,dl,dr,x);
			if(mr>mid)modify(rs[p],mid+1,tr,ml,mr,dl,dr,x);
		}
	}
	mat query(int p,int tl,int tr,int k){
		if(tl==tr)return tag[p][0];
		else {
			pushdown(p);
			int mid=(tl+tr)>>1;
			if(k<=mid)return query(ls[p],tl,mid,k);
			else return query(rs[p],mid+1,tr,k);
		}
	}
	int cnt;
	int build(int l,int r){
		int p=++cnt;
		if(l!=r){
			int mid=(l+r)>>1;
			ls[p]=build(l,mid);
			rs[p]=build(mid+1,r);
			ld[p]=min(ld[ls[p]],ld[rs[p]]);
		}
		else ld[p]=dep[rd[l]];
		return p;
	}
}
void build(int x){
	sz[x]=1;
	for (int i:g[x]){
		if(i==fa[x])continue;
		dep[i]=dep[x]+1;
		fa[i]=x;
		build(i);
		sz[x]+=sz[i];
	}
}
void deco(int x){
	dfn[x]=++tick;
	rd[tick]=x;
	if(!top[x])top[x]=x;
	hson[x]=0;
	for (int i:g[x]){
		if(i==fa[x])continue;
		if(sz[i]>sz[hson[x]])hson[x]=i;
	}
	if(hson[x]){
		top[hson[x]]=top[x];
		deco(hson[x]);
	}
	for (int i:g[x]){
		if(i==fa[x])continue;
		if(i!=hson[x])deco(i);
	}
}
void modline(int x,int y,st::mat k){
	// we calculate the lca of x y when we are modifying lol
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])swap(x,y);
		// jump y
		st::modify(1,1,n,dfn[top[y]],dfn[y],-1,-1,k);
		y=fa[top[y]];
	}
	if(dep[x]>dep[y])swap(x,y);
	st::modify(1,1,n,dfn[x],dfn[y],-1,-1,k);
}
int main(){
	iosoptim
	cin>>sub>>n>>q;
	int u,v;
	F(i,1,n-1){
		cin>>u>>v;
		g[u].pub(v);
		g[v].pub(u);
	}
	F(i,1,n)cin>>a[i];
	
	dep[1]=1;
	build(1);
	deco(1);
	st::build(1,n);
	
	int op,x,y,z,w;
	while(q--){
		cin>>op;
		if(op==1){
			cin>>x;
			st::mat res=st::query(1,1,n,dfn[x]);
			cout<<(res.k*a[x]+res.b)<<"\n";
		}
		else if(op==4){
			cin>>x>>y>>z>>w;
			modline(x,y,{z,w});
		}
		else if(op==3){
			cin>>x>>y>>z;
			st::modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,-1,-1,{y,z});
		}
		else {
			cin>>x>>y>>z>>w;
			int lb=-1,rb=-1;
			while(x&&(y>=0)){
				if(lb==-1)st::modify(1,1,n,dfn[x],dfn[x]+sz[x]-1,dep[x],dep[x]+y,{z,w});
				else {
					st::modify(1,1,n,dfn[x],lb-1,dep[x],dep[x]+y,{z,w});
					if(rb<dfn[x]+sz[x])st::modify(1,1,n,rb,dfn[x]+sz[x]-1,dep[x],dep[x]+y,{z,w});
				}
				lb=dfn[x];
				rb=dfn[x]+sz[x];
				x=fa[x];
				y--;
			}
		}
	}
	
	return 0;
}
0