結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー |
![]() |
提出日時 | 2024-10-15 22:23:02 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#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; }