結果
| 問題 |
No.2342 Triple Tree Query (Hard)
|
| ユーザー |
 lmxyue
|
| 提出日時 | 2025-08-29 14:08:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 769 ms / 10,000 ms |
| コード長 | 5,282 bytes |
| コンパイル時間 | 1,873 ms |
| コンパイル使用メモリ | 198,912 KB |
| 実行使用メモリ | 53,440 KB |
| 最終ジャッジ日時 | 2025-08-29 14:08:47 |
| 合計ジャッジ時間 | 26,953 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 36 |
コンパイルメッセージ
main.cpp: In member function ‘tag tag::operator+(tag)’:
main.cpp:12:34: warning: narrowing conversion of ‘(((1 * ((long long int)((tag*)this)->tag::k)) * ((long long int)d.tag::k)) % ((long long int)((int)mod)))’ from ‘long long int’ to ‘int’ [-Wnarrowing]
12 | return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
| ~~~~~~~~~^~~~
main.cpp:12:54: warning: narrowing conversion of ‘((((1 * ((long long int)((tag*)this)->tag::b)) * ((long long int)d.tag::k)) + ((long long int)d.tag::b)) % ((long long int)((int)mod)))’ from ‘long long int’ to ‘int’ [-Wnarrowing]
12 | return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
| ~~~~~~~~~~~~~~~^~~~
main.cpp: In function ‘int main()’:
main.cpp:150:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
150 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:152:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
152 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:157:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
157 | scanf("%d",&d[i]);
| ~~~~~^~~~~~~~~~~~
main.cpp:164:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
164 | scanf("%d%d",&op,&x);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:169:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
169 | scanf("%d%d%d",&y,&k,&b);
| ~~~~~^~~
ソースコード
#include<bits/stdc++.h>
using namespace std;
const int N=100010,mod=998244353;
int n,d[N],cnt,tot,first[N],nnext[N<<1],to[N<<1],dep[N],f[N],siz[N],son[N],top[N],seg[N],rev[N],pdep[N<<2];
struct tag{
int k,b;
tag(int _k=1,int _b=0){
k=_k;
b=_b;
}
tag operator+(tag d){
return {1ll*k*d.k%mod,(1ll*b*d.k+d.b)%mod};
}
void operator+=(tag d){
*this=*this+d;
}
bool operator!=(tag d){
return k!=d.k||b!=d.b;
}
}p[N<<2][12];
void add(int x,int y){
nnext[++tot]=first[x];
first[x]=tot;
to[tot]=y;
}
void dfs1(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
for(int e=first[u];e;e=nnext[e]){
if(to[e]!=fa){
dfs1(to[e],u);
siz[u]+=siz[to[e]];
if(siz[to[e]]>siz[son[u]]){
son[u]=to[e];
}
}
}
}
void dfs2(int u){
if(son[u]){
top[son[u]]=top[u];
seg[son[u]]=++cnt;
rev[cnt]=son[u];
dfs2(son[u]);
}
for(int e=first[u];e;e=nnext[e]){
if(!top[to[e]]){
seg[to[e]]=++cnt;
top[to[e]]=rev[cnt]=to[e];
dfs2(to[e]);
}
}
}
void build(int l,int r,int rt){
int mid=(l+r)>>1;
if(l==r){
p[rt][0]={0,d[rev[l]]};
pdep[rt]=dep[rev[l]];
return;
}
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pdep[rt]=min(pdep[rt<<1],pdep[rt<<1|1]);
}
void laz(int rt,int pos,tag now){
if(pos>=pdep[rt]){
p[rt][pos-pdep[rt]]+=now;
}
}
void pushdown(int rt){
for(int i=0;i<=10;i++){
if(p[rt][i]!=(tag){1,0}){
laz(rt<<1,i+pdep[rt],p[rt][i]);
laz(rt<<1|1,i+pdep[rt],p[rt][i]);
p[rt][i]={1,0};
}
}
if(p[rt][11]!=(tag){1,0}){
for(int i=0;i<=11;i++){
if(i+pdep[rt<<1]-pdep[rt]>10){
p[rt<<1][i]+=p[rt][11];
}
if(i+pdep[rt<<1|1]-pdep[rt]>10){
p[rt<<1|1][i]+=p[rt][11];
}
}
p[rt][11]={1,0};
}
}
void update(int x,int y,int pos,int k,int b,int l,int r,int rt){
int mid=(l+r)>>1;
if(x<=l&&y>=r){
if(pos==-1){
for(int i=0;i<=11;i++){
p[rt][i]+={k,b};
}
}
else{
laz(rt,pos,{k,b});
}
return;
}
pushdown(rt);
if(x<=mid){
update(x,y,pos,k,b,l,mid,rt<<1);
}
if(y>=mid+1){
update(x,y,pos,k,b,mid+1,r,rt<<1|1);
}
}
int query(int x,int l,int r,int rt){
int mid=(l+r)>>1;
if(l==r){
return p[rt][0].b;
}
pushdown(rt);
return x<=mid?query(x,l,mid,rt<<1):query(x,mid+1,r,rt<<1|1);
}
void change(int x,int y,int k,int b){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
update(seg[top[x]],seg[x],-1,k,b,1,n,1);
x=f[top[x]];
}
if(dep[x]>dep[y]){
swap(x,y);
}
update(seg[x],seg[y],-1,k,b,1,n,1);
}
void modify(int x,int y,int k,int b){
for(int i=0;i<=y;i++){
update(seg[x],seg[x]+siz[x]-1,dep[x]+y-i,k,b,1,n,1);
if(i!=y){
update(seg[x],seg[x]+siz[x]-1,dep[x]+y-i-1,k,b,1,n,1);
}
x=f[x];
if(!x){
for(int j=i+2;j<=y;j++){
update(seg[1],seg[1]+siz[1]-1,dep[1]+y-j,k,b,1,n,1);
}
break;
}
}
}
int main(){
int q,a,b,op,x,y,k;
scanf("%d%d",&n,&q);
for(int i=1;i<=n-1;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
}
dfs1(1,0);
cnt=seg[1]=rev[1]=top[1]=1;
dfs2(1);
build(1,n,1);
while(q--){
scanf("%d%d",&op,&x);
if(op==1){
printf("%d\n",query(seg[x],1,n,1));
}
else if(op==2){
scanf("%d%d%d",&y,&k,&b);
modify(x,y,k,b);
}
else if(op==3){
scanf("%d%d",&k,&b);
update(seg[x],seg[x]+siz[x]-1,-1,k,b,1,n,1);
}
else{
scanf("%d%d%d",&y,&k,&b);
change(x,y,k,b);
}
}
}