結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー | vjudge1 |
提出日時 | 2024-10-15 22:23:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,279 ms / 10,000 ms |
コード長 | 3,658 bytes |
コンパイル時間 | 2,834 ms |
コンパイル使用メモリ | 212,624 KB |
実行使用メモリ | 66,048 KB |
最終ジャッジ日時 | 2024-10-15 22:24:35 |
合計ジャッジ時間 | 55,277 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 34 ms
5,248 KB |
testcase_03 | AC | 30 ms
5,248 KB |
testcase_04 | AC | 27 ms
5,248 KB |
testcase_05 | AC | 29 ms
5,248 KB |
testcase_06 | AC | 32 ms
5,248 KB |
testcase_07 | AC | 2,034 ms
59,136 KB |
testcase_08 | AC | 2,033 ms
59,008 KB |
testcase_09 | AC | 2,036 ms
59,136 KB |
testcase_10 | AC | 2,145 ms
59,008 KB |
testcase_11 | AC | 2,132 ms
59,136 KB |
testcase_12 | AC | 2,121 ms
59,136 KB |
testcase_13 | AC | 2,138 ms
59,008 KB |
testcase_14 | AC | 2,161 ms
59,136 KB |
testcase_15 | AC | 2,279 ms
59,008 KB |
testcase_16 | AC | 2,152 ms
59,008 KB |
testcase_17 | AC | 1,163 ms
64,000 KB |
testcase_18 | AC | 1,056 ms
66,048 KB |
testcase_19 | AC | 1,055 ms
63,744 KB |
testcase_20 | AC | 1,050 ms
65,152 KB |
testcase_21 | AC | 1,054 ms
66,048 KB |
testcase_22 | AC | 898 ms
58,624 KB |
testcase_23 | AC | 907 ms
58,752 KB |
testcase_24 | AC | 906 ms
58,624 KB |
testcase_25 | AC | 1,455 ms
59,136 KB |
testcase_26 | AC | 1,519 ms
59,264 KB |
testcase_27 | AC | 1,446 ms
59,136 KB |
testcase_28 | AC | 1,463 ms
59,136 KB |
testcase_29 | AC | 1,476 ms
59,264 KB |
testcase_30 | AC | 907 ms
59,008 KB |
testcase_31 | AC | 919 ms
59,136 KB |
testcase_32 | AC | 909 ms
59,008 KB |
testcase_33 | AC | 1,301 ms
59,008 KB |
testcase_34 | AC | 1,225 ms
59,136 KB |
testcase_35 | AC | 1,357 ms
59,008 KB |
testcase_36 | AC | 1,528 ms
59,008 KB |
testcase_37 | AC | 1,176 ms
59,008 KB |
ソースコード
#include<bits/stdc++.h> #define fun int p,int l,int r #define ls p<<1 #define rs p<<1|1 #define lfun ls,l,mid #define rfun rs,mid+1,r #define For(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; typedef long long ll; const int N=1e5+5,mod=998244353,INF=1e9; int n,T,sub; int tot,head[N],to[N<<1],nxt[N<<1]; int id[N],dfn,top[N],siz[N],son[N],fa[N],rk[N],dep[N]; ll a[N]; inline void add(int u,int v){nxt[++tot]=head[u],to[tot]=v,head[u]=tot;} struct oper{ ll k,b; inline oper operator +(const oper P){return {k*P.k%mod,(b*P.k+P.b)%mod};} inline void operator +=(oper v){*this=*this+v;} }tag[N<<2][11],ent[N<<2]; int md[N<<2]; void dfs1(int u){ siz[u]=1; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(v==fa[u])continue; dep[v]=dep[u]+1;fa[v]=u; dfs1(v); siz[u]+=siz[v]; if(siz[son[u]]<siz[v])son[u]=v; } } void dfs2(int u,int topu){ id[u]=++dfn;top[u]=topu;rk[dfn]=u; if(!son[u])return ; dfs2(son[u],topu); for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(v!=son[u]&&v!=fa[u])dfs2(v,v); } } inline void atag(int p,oper V,int now_d){ if(now_d==INF){//normal ent[p]+=V; for(int i=0;i<=10;i++)tag[p][i]+=V; // cout<<V.b<<"?\n"; } else if(!now_d)ent[p]+=V;//,cout<<p<<" "<<ent[p].k<<" "<<ent[p].b<<"why\n"; else if(now_d>=md[p]&&now_d<=md[p]+10)tag[p][now_d-md[p]]+=V;//dep } const oper U={1,0}; inline void pd(int p){ for(int i=0;i<=10;i++){ atag(ls,tag[p][i],md[p]+i); atag(rs,tag[p][i],md[p]+i); // cout<<p<<" "<<i<<" "<<tag[p][i].k<<" "<<tag[p][i].b<<"???\n"; tag[p][i]=U; } atag(ls,ent[p],0);atag(rs,ent[p],0); // cout<<p<<" "<<ent[p].k<<" "<<ent[p].b<<"????\n"; for(int i=0;i<=10;i++){ if(md[ls]+i>md[p]+10)atag(ls,ent[p],md[ls]+i); if(md[rs]+i>md[p]+10)atag(rs,ent[p],md[rs]+i); } ent[p]=U; } inline void pu(int p){md[p]=min(md[ls],md[rs]);} inline void build(fun){ for(int i=0;i<=10;i++)tag[p][i]=U; ent[p]=U; if(l==r)return md[p]=dep[rk[l]],void(); int mid=(l+r)>>1; build(lfun),build(rfun); pu(p); } inline void upd(fun,int x,int y,oper V,int px,int py){ if(x>y)return ; if(x<=l&&r<=y){ if(px==INF)return atag(p,V,INF); else{ for(int i=px;i<=py;i++)atag(p,V,i); } return ; } int mid=(l+r)>>1; pd(p); if(x<=mid)upd(lfun,x,y,V,px,py); if(y>mid)upd(rfun,x,y,V,px,py); } inline oper qry(fun,int x){ // cout<<p<<" "<<l<<" "<<r<<" "<<ent[p].k<<" "<<ent[p].b<<"\n"; if(l==r)return tag[p][0]; pd(p); int mid=(l+r)>>1; if(x<=mid)return qry(lfun,x); return qry(rfun,x); } inline void swap(int &u,int &v){u^=v^=u^=v;} inline void chain(int u,int v,oper V){ while(top[u]^top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); upd(1,1,n,id[top[u]],id[u],V,INF,0); u=fa[top[u]]; } if(dep[u]>dep[v])swap(u,v); upd(1,1,n,id[u],id[v],V,INF,0); } int main(){ // freopen("tour10.in","r",stdin); // freopen("tour.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>T; dep[1]=1; int u,v; for(int i=1;i<n;i++){ cin>>u>>v; add(u,v),add(v,u); } for(int i=1;i<=n;i++)cin>>a[i]; dfs1(1),dfs2(1,1);build(1,1,n); int op,x,y,k,b,r; for(int i=1;i<=T;i++){ cin>>op>>x; if(op==1){ oper P=qry(1,1,n,id[x]); cout<<(P.k*a[x]+P.b)%mod<<"\n"; } else if(op==4){ cin>>y>>k>>b; chain(x,y,{k,b}); } else if(op==3){ cin>>k>>b; upd(1,1,n,id[x],id[x]+siz[x]-1,{k,b},INF,0); } else{ cin>>r>>k>>b; int L=0,R=0; for(;(~r)&&x;r--){ if(L){ upd(1,1,n,id[x],L-1,{k,b},dep[x],dep[x]+r); // if(id[x]+siz[x]-1) upd(1,1,n,R+1,id[x]+siz[x]-1,{k,b},dep[x],dep[x]+r); } else upd(1,1,n,id[x],id[x]+siz[x]-1,{k,b},dep[x],dep[x]+r); L=id[x],R=id[x]+siz[x]-1;x=fa[x]; // cout<<x<<"\n"; } } } return 0; }