結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー | vjudge1 |
提出日時 | 2024-10-16 13:28:51 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,044 bytes |
コンパイル時間 | 2,767 ms |
コンパイル使用メモリ | 161,532 KB |
実行使用メモリ | 817,920 KB |
最終ジャッジ日時 | 2024-10-16 13:29:04 |
合計ジャッジ時間 | 9,495 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | MLE | - |
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 | -- | - |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=100005,mod=998244353,INF=0x3f3f3f3f; int head[N],cnt,a[N],sz[N],son[N],top[N],dfn[N],tot,Fa[N],deps[N],arr[N]; struct edge{ int v,next; }e[N<<1]; void add_edge(int u,int v){ e[cnt]=edge{v,head[u]}; head[u]=cnt++; } void DFS(int u,int fa){ sz[u]=1; son[u]=-1; Fa[u]=fa; for(int i=head[u];~i;i=e[i].next){ const int v=e[i].v; if(v==fa) continue; deps[v]=deps[u]+1; DFS(v,u); sz[u]+=sz[v]; if(son[u]==-1 || sz[son[u]]<sz[v]) son[u]=v; } } void dfs(int u,int fa){ if(fa==-1 || son[fa]!=u) top[u]=u; else top[u]=top[fa]; arr[tot]=u; dfn[u]=tot++; if(son[u]!=-1) dfs(son[u],u); for(int i=head[u];~i;i=e[i].next){ const int v=e[i].v; if(v==fa || v==son[u]) continue; dfs(v,u); } } struct AAA{ int k,b; }; int calc(int x,AAA aa){return (1ll*aa.k*x%mod+aa.b)%mod;} AAA merge(AAA aa,AAA bb){return AAA{int(1ll*aa.k*bb.k%mod),int((1ll*bb.k*aa.b%mod+bb.b)%mod)};} namespace seg{ struct node{ node *left,*right; int val,mn,l,r; AAA tag[12]; }pool[N<<2],*root=nullptr; int cnt; node* New(int x,int deps,int l,int r){ pool[cnt]=node{nullptr,nullptr,x,deps,l,r,{}}; for(int i=0;i<12;++i) pool[cnt].tag[i]=AAA{1,0}; return pool+(cnt++); } node* build(int l,int r){ if(l+1==r) return New(a[arr[l]],deps[arr[l]],l,r); int mid=l+(r-l)/2; node* p=New(0,0,l,r); p->left=build(l,mid); p->right=build(mid,r); p->mn=min(p->left->mn,p->right->mn); return p; } void add_tag(node* p,int dis,AAA aa){ if(p==nullptr || (aa.k==1 && aa.b==0)) return; if(p->l+1==p->r && dis==0) p->val=calc(p->val,aa); p->tag[dis]=merge(p->tag[dis],aa); } void push_down(node* p){ if(p==nullptr) return; for(int i=0;i<12;++i){ if(p->tag[i].k==1 && p->tag[i].b==0) continue; if(i==11){ for(int j=max(0,p->mn+11-p->left->mn);j<12;++j) add_tag(p->left,j,p->tag[i]); for(int j=max(0,p->mn+11-p->right->mn);j<12;++j) add_tag(p->right,j,p->tag[i]); }else{ if(p->mn+i-p->left->mn>=0) add_tag(p->left,p->mn+i-p->left->mn,p->tag[i]); if(p->mn+i-p->right->mn>=0) add_tag(p->right,p->mn+i-p->right->mn,p->tag[i]); } p->tag[i]=AAA{1,0}; } } int query(node* p,int l,int r,int pos){ if(l+1==r) return p->val; push_down(p); int mid=l+(r-l)/2; if(pos<mid) return query(p->left,l,mid,pos); return query(p->right,mid,r,pos); } void update(node* p,int L,int R,int l,int r,int deps,AAA aa){ if(l>=r) return; if(l<=L && R<=r){ if(deps==INF){ for(int i=0;i<12;++i) add_tag(p,i,aa); }else if(deps>=p->mn) add_tag(p,deps-p->mn,aa); return; } push_down(p); int mid=L+(R-L)/2; if(l<mid) update(p->left,L,mid,l,r,deps,aa); if(r>mid) update(p->right,mid,R,l,r,deps,aa); } } int main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); memset(head,255,sizeof(head)); int Sub,n,q; cin >> Sub >> n >> q; for(int i=0,u,v;i<n-1;++i){ cin >> u >> v; --u; --v; add_edge(u,v); add_edge(v,u); } for(int i=0;i<n;++i) cin >> a[i]; deps[0]=0; DFS(0,-1); dfs(0,-1); seg::root=seg::build(0,n); while(q--){ int op,u,v,k,b,r; cin >> op; if(op==1){ cin >> u; --u; cout << seg::query(seg::root,0,n,dfn[u]) << '\n'; }else if(op==4){ cin >> u >> v >> k >> b; --u; --v; while(top[u]!=top[v]){ if(deps[top[u]]<deps[top[v]]) swap(u,v); seg::update(seg::root,0,n,dfn[top[u]],dfn[u]+1,INF,AAA{k,b}); u=Fa[top[u]]; } if(dfn[u]>dfn[v]) swap(u,v); seg::update(seg::root,0,n,dfn[u],dfn[v]+1,INF,AAA{k,b}); }else if(op==3){ cin >> u >> k >> b; --u; seg::update(seg::root,0,n,dfn[u],dfn[u]+sz[u],INF,AAA{k,b}); }else{ cin >> u >> r >> k >> b; --u; for(int num=0;num<=r;++num){ if(num<r && u==0){ for(int i=r-num;i>=0;--i) seg::update(seg::root,0,n,dfn[u],dfn[u]+sz[u],deps[u]+i,AAA{k,b}); break; }else{ seg::update(seg::root,0,n,dfn[u],dfn[u]+sz[u],deps[u]+r-num,AAA{k,b}); if(num<r) seg::update(seg::root,0,n,dfn[u],dfn[u]+sz[u],deps[u]+r-num-1,AAA{k,b}); } u=Fa[u]; } } } return 0; }