結果

問題 No.2342 Triple Tree Query (Hard)
コンテスト
ユーザー BitByBit
提出日時 2026-01-12 09:33:46
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,093 ms / 10,000 ms
コード長 10,982 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,210 ms
コンパイル使用メモリ 356,120 KB
実行使用メモリ 317,456 KB
最終ジャッジ日時 2026-01-12 09:34:17
合計ジャッジ時間 28,609 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#ifndef LIBRARY_HPP
#define LIBRARY_HPP
#define fi first
#define se second
namespace lib
{
	using namespace std;
	using i8=int8_t;
	using i16=int16_t;
	using i32=int32_t;
	using i64=int64_t;
	using i128=__int128_t;
	using u8=uint8_t;
	using u16=uint16_t;
	using u32=uint32_t;
	using u64=uint64_t;
	using u128=__uint128_t;
	using f32=float;
	using f64=double;
	using f80=long double;
	using f128=__float128;
	using uint=unsigned int;
	using ll=long long;
	using ull=unsigned long long;
	using ld=long double;
	class null_t{};
	constexpr null_t null_v;
	template<typename type>
	constexpr type inf=numeric_limits<type>::max()/2;
	template<typename function>
	void multitest(function &&main)
	{
		int tests;
		cin>>tests;
		for(int test_case=1;test_case<=tests;test_case++)main(test_case);
	}
	template<typename function>
	void multitest(int tests,function &&main)
	{
		for(int test_case=1;test_case<=tests;test_case++)main(test_case);
	}
}
#endif
#ifndef SEGTREE_HPP
#define SEGTREE_HPP
namespace lib
{
	template<typename val_t,typename tag_t,typename operation_fn,typename mapping_fn,typename composition_fn,typename untagged_fn>
	class lazy_segtree
	{
	private:
		using value_type=val_t;
		using tag_type=tag_t;
		  operation_fn operation{};
		  mapping_fn mapping{};
		  composition_fn composition{};
		  untagged_fn untagged{};
		int n;
		vector<val_t>values;
		vector<tag_t>tags;
		inline __attribute__((always_inline)) int ls(int &x)
		{
			return x<<1;
		}
		inline __attribute__((always_inline)) int rs(int &x)
		{
			return x<<1|1;
		}
		void push_up(int &x)
		{
			values[x]=operation(values[ls(x)],values[rs(x)]);
		}
		void add_tag(int x,int l,int r,tag_t &tag)
		{
			values[x]=mapping(values[x],tag,r-l+1);
			tags[x]=composition(tags[x],tag);
		}
		void push_down(int &x,int &l,int &r)
		{
			if(!untagged(tags[x]))
			{
				int mid=(l+r)>>1;
				add_tag(ls(x),l,mid,tags[x]);
				add_tag(rs(x),mid+1,r,tags[x]);
				tags[x]=make_pair(1,0);
			}
		}
		template<typename lambda>
		void build(lambda &&func,int x,int l,int r)
		{
			tags[x]=make_pair(1,0);
			if(l==r)return values[x]=func(l),[]{}();
			int mid=(l+r)>>1;
			build(func,ls(x),l,mid);
			build(func,rs(x),mid+1,r);
			push_up(x);
		}
		void update(int &_l,int &_r,tag_t &t,int x,int l,int r)
		{
			if(_l<=l&&r<=_r)return add_tag(x,l,r,t);
			push_down(x,l,r);
			int mid=(l+r)>>1;
			if(_l<=mid)update(_l,_r,t,ls(x),l,mid);
			if(mid<_r)update(_l,_r,t,rs(x),mid+1,r);
			push_up(x);
		}
		val_t query(int &_l,int &_r,int x,int l,int r)
		{
			if(_l<=l&&r<=_r)return values[x];
			push_down(x,l,r);
			int mid=(l+r)>>1;
			if(_l<=mid&&mid<_r)return operation(query(_l,_r,ls(x),l,mid),query(_l,_r,rs(x),mid+1,r));
			else if(_l<=mid)return query(_l,_r,ls(x),l,mid);
			else return query(_l,_r,rs(x),mid+1,r);
		}
	public:
		lazy_segtree():n(0){}
		lazy_segtree(int _n)
		{
			resize(_n);
		}
		template<typename lambda>
		lazy_segtree(int _n,lambda &&func)
		{
			resize(_n);
			build(func);
		}
		int size()
		{
			return n;
		}
		void resize(int _n)
		{
			n=_n;
			values.resize((n<<2)+1);
			tags.resize((n<<2)+1);
		}
		template<typename lambda>
		void build(lambda &&func)
		{
			build(func,1,1,n);
		}
		void update(int l,int r,tag_t &t)
		{
			update(l,r,t,1,1,n);
		}
		val_t query(int l,int r)
		{
			return query(l,r,1,1,n);
		}
	};
}
#endif
#ifndef MODINT_HPP
#define MODINT_HPP
namespace lib
{
	template<typename uint_t,uint_t m>
	struct static_modint
	{
		static_assert(is_integral<uint_t>::value&&is_unsigned<uint_t>::value);
		uint_t x;
		static constexpr uint_t mod()
		{
			return m;
		}
		constexpr static_modint():x(0){}
		constexpr static_modint(ll _x)
		{
			_x%=mod();
			if(_x<0)_x+=mod();
			x=_x;
		}
		uint_t val()const
		{
			return x;
		}
		static_modint &operator++()
		{
			x++;
			if (x==mod())x=0;
			return *this;
		}
		static_modint &operator--()
		{
			if(x==0)x=mod();
			x--;
			return *this;
		}
		static_modint operator++(int)
		{
			static_modint res=*this;
			++*this;
			return res;
		}
		static_modint operator--(int)
		{
			static_modint res=*this;
			--*this;
			return res;
		}
		static_modint &operator+=(const static_modint &y)
		{
			x+=y.x;
			if(x>=mod())x-=mod();
			return *this;
		}
		static_modint &operator-=(const static_modint &y)
		{
			if(x<y.x)x+=mod();
			x-=y.x;
			return *this;
		}
		template<typename uint_t2>
		typename enable_if<is_same<uint_t2,uint>::value,static_modint>::type &operator*=(const static_modint<uint_t2,m>&y)
		{
			static_assert(is_same<uint_t,uint_t2>::value);
			x=(ll)x*y.x%mod();
			return *this;
		}
		template<typename uint_t2>
		typename enable_if<is_same<uint_t2,ull>::value,static_modint>::type &operator*=(const static_modint<uint_t2,m>&y)
		{
			static_assert(is_same<uint_t,uint_t2>::value);
			x=(__int128)x*y.x%mod();
			return *this;
		}
		static_modint pow(ll x)const
		{
			static_modint y=*this,z=1;
			for(;x;x>>=1,y*=y)if(x&1)z*=y;
			return z;
		}
		static_modint inv()const
		{
			return pow(mod()-2);
		}
		static_modint &operator/=(const static_modint &y)
		{
			return *this=*this*y.inv();
		}
		static_modint operator+()const
		{
			return *this;
		}
		static_modint operator-()const
		{
			return static_modint()-*this;
		}
		friend static_modint operator+(const static_modint &x,const static_modint &y)
		{
			return static_modint(x)+=y;
		}
		friend static_modint operator-(const static_modint &x,const static_modint &y)
		{
			return static_modint(x)-=y;
		}
		friend static_modint operator*(const static_modint &x,const static_modint &y)
		{
			return static_modint(x)*=y;
		}
		friend static_modint operator/(const static_modint &x,const static_modint &y)
		{
			return static_modint(x)/=y;
		}
		friend bool operator==(const static_modint &x,const static_modint &y)
		{
			return x.x==y.x;
		}
		friend bool operator!=(const static_modint &x,const static_modint &y)
		{
			return x.x!=y.x;
		}
		friend bool operator<(const static_modint &x,const static_modint &y)
		{
			return x.x<y.x;
		}
		template<typename istream_t>
		friend istream_t &operator>>(istream_t &input,static_modint &x)
		{
			ll y;
			input>>y;
			x=static_modint(y);
			return input;
		}
		template<typename ostream_t>
		friend ostream_t &operator<<(ostream_t &output,const static_modint &x)
		{
			return output<<x.val();
		}
	};
}
#endif
using namespace std;
using namespace lib;
int n,q,k,dfn;
constexpr int N=100010,L=110;
array<int,N>Fa,Son,Dfn,Rnk,Size,Dep,Top;
array<array<int,L>,N>N_son,N_dfn,N_dfn0,N_dfn1,N_sz,N_sz0,N_sz1;
array<int,N>F_dfn0,F_dfn1,F_sz0,F_sz1;
vector<basic_string<int>>G;
void chkmin(int &x,const int y)
{
	if(y)
	{
		if(x)x=min(x,y);
		else x=y;
	}
}
bool get_type(int x)
{
	return Dep[x]-Dep[Top[x]]<=k;
}
void dfs_initial(int x,int f)
{
	Dep[x]=Dep[Fa[x]=f]+1;
	Size[x]=1;
	for(int y:G[x])
		if(y!=f)
		{
			dfs_initial(y,x);
			Size[x]+=Size[y];
			if(Size[y]>Size[Son[x]])Son[x]=y;
		}
}
void dfs_hld(int x,int t)
{
	Top[x]=t;
	if(Son[x])dfs_hld(Son[x],t);
	for(int y:G[x])if(y!=Fa[x]&&y!=Son[x])dfs_hld(y,y);
}
void bfs(int s)
{
	deque<int>Q;
	Q.push_back(s);
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop_front();
		if(get_type(x))
		{
			if(!Dfn[x])Rnk[Dfn[x]=++dfn]=x;
			if(!N_dfn[s][Dep[x]-Dep[s]])N_dfn[s][Dep[x]-Dep[s]]=Dfn[x];
		}
		if(Dep[x]-Dep[s]<k)for(int y:G[x])if(y!=Fa[x])Q.push_back(y);
	}
}
void dfs_bfs(int x)
{
	bfs(x);
	for(int y:G[x])if(y!=Fa[x])dfs_bfs(y);
}
void dfs_dfs(int x)
{
	if(!Dfn[x])Rnk[Dfn[x]=++dfn]=x;
	if(Son[x])dfs_dfs(Son[x]);
	for(int y:G[x])if(y!=Fa[x]&&y!=Son[x])dfs_dfs(y);
}
void dfs_final(int x)
{
	N_son[x][0]=x;
	for(int i=1;i<=k;i++)N_son[x][i]=Son[N_son[x][i-1]];
	N_sz[x][0]=1;
	N_dfn[x][0]=Dfn[x];
	if(get_type(x))++N_sz0[x][0],N_dfn0[x][0]=Dfn[x];
	else ++N_sz1[x][0],N_dfn1[x][0]=Dfn[x];
	for(int y:G[x])
		if(y!=Fa[x])
		{
			dfs_final(y);
			for(int i=1;i<=k;i++)N_sz[x][i]+=N_sz[y][i-1];
			F_sz0[x]+=F_sz0[y];
			F_sz1[x]+=F_sz1[y];
			chkmin(F_dfn0[x],F_dfn0[y]);
			chkmin(F_dfn1[x],F_dfn1[y]);
			for(int i=1;i<=k+1;i++)
			{
				N_sz0[x][i]+=N_sz0[y][i-1];
				N_sz1[x][i]+=N_sz1[y][i-1];
				chkmin(N_dfn[x][i],N_dfn[y][i-1]);
				chkmin(N_dfn0[x][i],N_dfn0[y][i-1]);
				chkmin(N_dfn1[x][i],N_dfn1[y][i-1]);
			}
			chkmin(F_dfn0[x],N_dfn0[x][k+1]);
			chkmin(F_dfn1[x],N_dfn1[x][k+1]);
		}
	F_sz0[x]+=N_sz0[x][k+1];
	F_sz1[x]+=N_sz1[x][k+1];
}
using mint=lib::static_modint<uint,998244353>;
struct tmp
{
	pair<mint,mint>operator()(pair<mint,mint>x,pair<mint,mint>y)
	{
		return make_pair(x.fi*y.fi,x.se*y.fi+y.se);
	};
};
struct tmp2
{
	pair<mint,mint>operator()(pair<mint,mint>x,pair<mint,mint>y,int sz)
	{
		return make_pair(x.fi*y.fi,x.se*y.fi+y.se);
	};
};
struct tmp3
{
	bool operator()(pair<mint,mint>x)
	{
		return x.fi.val()==1&&x.se.val()==0;
	};
};
using segt=lib::lazy_segtree<pair<mint,mint>,pair<mint,mint>,tmp,tmp2,tmp,tmp3>;
segt T;
array<mint,N>A;
void f(int x,int d,pair<mint,mint>p)
{
	if(d<0)return;
	if(!N_sz[x][d])return;
	if(N_son[x][d]&&!get_type(N_son[x][d]))
	{
		T.update(Dfn[N_son[x][d]],Dfn[N_son[x][d]],p);
		if(N_sz[x][d]>1)T.update(N_dfn[x][d],N_dfn[x][d]+N_sz[x][d]-2,p);
	}
	else T.update(N_dfn[x][d],N_dfn[x][d]+N_sz[x][d]-1,p);
}
void g(int x,int y,pair<mint,mint>p)
{
	while(x!=y&&Dep[x]-Dep[Top[y]]<=k)
	{
		T.update(Dfn[x],Dfn[x],p);
		x=Son[x];
	}
	T.update(Dfn[x],Dfn[y],p);
}
void update_neighbour(int x,int d,pair<mint,mint>p)
{
	for(int i=0;i<=d;i++)
	{
		if(x<1)f(1,d-i+x-1,p),f(1,d-i+x-2,p);
		else f(x,d-i,p),f(x,d-i-1,p);
		if(x>1)x=Fa[x];
		else --x;
	}
}
void update_subtree(int x,pair<mint,mint>p)
{
	for(int i=0;i<=k;i++)f(x,i,p);
	if(F_sz0[x])T.update(F_dfn0[x],F_dfn0[x]+F_sz0[x]-1,p);
	if(F_sz1[x])T.update(F_dfn1[x],F_dfn1[x]+F_sz1[x]-1,p);
}
void update_path(int x,int y,pair<mint,mint>p)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]])swap(x,y);
		g(Top[x],x,p);
		x=Fa[Top[x]];
	}
	if(Dep[x]>Dep[y])swap(x,y);
	g(x,y,p);
}
i32 main(int argc,char *argv[])
{
	// freopen("../tree/tree6.in","r",stdin);
	// freopen("f.out","w",stdout);
	// if(argc==3)freopen(argv[1],"r",stdin),freopen(argv[2],"w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	k=10;
	G.resize(n+1);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++)cin>>A[i];
	dfs_initial(1,0);
	dfs_hld(1,1);
	dfs_bfs(1);
	dfs_dfs(1);
	dfs_final(1);
	T.resize(n);
	T.build([](int x[[maybe_unused]]){return make_pair(1,0);});
	while(q--)[&]
	{
		int opt;
		cin>>opt;
		switch(opt)
		{
			case 1:
			{
				int x;
				cin>>x;
				pair<mint,mint>p=T.query(Dfn[x],Dfn[x]);
				cout<<A[x]*p.fi+p.se<<'\n';
				break;
			}
			case 2:
			{
				int x,d;
				pair<mint,mint>p;
				cin>>x>>d>>p.fi>>p.se;
				update_neighbour(x,d,p);
				break;
			}
			case 3:
			{
				int x;
				pair<mint,mint>p;
				cin>>x>>p.fi>>p.se;
				update_subtree(x,p);
				break;
			}
			case 4:
			{
				int x,y;
				pair<mint,mint>p;
				cin>>x>>y>>p.fi>>p.se;
				update_path(x,y,p);
			}
		}
	}();
	return 0;
}
0