結果
| 問題 |
No.2342 Triple Tree Query (Hard)
|
| コンテスト | |
| ユーザー |
 vjudge1
|
| 提出日時 | 2024-10-15 15:05:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | MLE * 1 -- * 1 |
| other | -- * 36 |
ソースコード
#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;
}