QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#586772 | #9373. Query on Tree | bessie_goes_moo | WA | 130ms | 77440kb | C++14 | 10.3kb | 2024-09-24 15:27:09 | 2024-09-24 15:27:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int al=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
al=al*10+ch-'0';
ch=getchar();
}
return al*fh;
}
const int N=2e5+10;
int MAX=0x7ffffffffffffff;
int MAX_CAN=4E14;
int num_edge,head[N],q[N],hed,til,al[N],dfn[N],T,n,Q,shu[N],fat[N][11],dfn_max[N],cnt,dui[N],lei;
struct bfN{
int z;
int upper[11],lower_l[11];
int lower_r[11];
}bfn[N];
struct Edge{
int to,next;
}edge[N*2];
struct node{
int z,l,r,laze_tag;
};
class seg_tree{
public:
node z[2*N];
void build(int now,int l,int r){
this->z[now].l=l;
this->z[now].r=r;
this->z[now].laze_tag=0;
this->z[now].z=0;
if(l!=r){
int mid=(l+r)/2;
this->build(now*2,l,mid);
this->build(now*2+1,mid+1,r);
}
}
void add(int now,int l,int r,int v){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l||l>r||r<=0)
return ;
if(ll==rr){
this->z[now].z+=v;
return ;
}
else if(ll>=l&&rr<=r){
this->z[now].laze_tag+=v;
return ;
}
else {
add(now*2,l,r,v);
add(now*2+1,l,r,v);
this->z[now].z=max(this->z[now*2].z+this->z[now*2].laze_tag,this->z[now*2+1].z+this->z[now*2+1].laze_tag);
}
}
int query(int now,int l,int r){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l||l>r||r<=0)
return -MAX;
if(ll==rr){
return this->z[now].z;
}
else if(ll>=l&&rr<=r){
return this->z[now].z+this->z[now].laze_tag;
}
else {
return max(query(now*2,l,r),query(now*2+1,l,r))+this->z[now].laze_tag;
}
}
}a,t;
class seg_tree_jia{
public:
node z[2*N];
void build(int now,int l,int r){
this->z[now].l=l;
this->z[now].r=r;
this->z[now].laze_tag=0;
this->z[now].z=0;
if(l!=r){
int mid=(l+r)/2;
this->build(now*2,l,mid);
this->build(now*2+1,mid+1,r);
}
}
void add(int now,int l,int r,int v){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l)
return ;
if(ll==rr){
this->z[now].z+=v;
return ;
}
else if(ll>=l&&rr<=r){
this->z[now].laze_tag+=v;
return ;
}
else {
add(now*2,l,r,v);
add(now*2+1,l,r,v);
}
}
int query(int now,int l,int r){
if(l<=0)
l=1;
if(l>r)
return 0;
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l)
return 0;
if(ll==rr){
return this->z[now].z;
}
else {
return query(now*2,l,r)+query(now*2+1,l,r)+this->z[now].laze_tag;
}
}
}b;
void add_edge(int from,int to){
edge[++num_edge].to=to;
edge[num_edge].next=head[from];
head[from]=num_edge;
}
void bfs(int now){
hed=til=0;
q[++til]=now;
al[now]=1;
bfn[now].z=++cnt;
dui[cnt]=now;
bfn[now].lower_l[0]=bfn[now].z;
bfn[now].lower_r[0]=bfn[now].z;
bfn[now].upper[0]=now;
while(hed<til){
hed++;
for(int i=head[q[hed]];i;i=edge[i].next){
if(al[edge[i].to]==0){
al[edge[i].to]=1;
bfn[edge[i].to].z=++cnt;
q[++til]=edge[i].to;
bfn[edge[i].to].lower_l[0]=cnt;
bfn[edge[i].to].lower_r[0]=cnt;
bfn[edge[i].to].upper[0]=edge[i].to;
for(int j=1;j<=10;j++){
bfn[edge[i].to].upper[j]=bfn[q[hed]].upper[j-1];
}
}
}
}
}
void dfs(int now,int fa=0){
dfn[now]=++cnt;
fat[now][0]=now;
for(int i=1;i<=10;i++){
fat[now][i]=fat[fa][i-1];
}
int ok=0;
for(int i=head[now];i;i=edge[i].next){
if(edge[i].to!=fa){
dfs(edge[i].to,now);
for(int j=1;j<=10;j++){
if(ok==0)
bfn[now].lower_l[j]=bfn[edge[i].to].lower_l[j-1],bfn[now].lower_r[j]=bfn[edge[i].to].lower_r[j-1];
else {
bfn[now].lower_l[j]=min(bfn[now].lower_l[j],bfn[edge[i].to].lower_l[j-1]);
bfn[now].lower_r[j]=max(bfn[now].lower_r[j],bfn[edge[i].to].lower_r[j-1]);
}
}
ok=1;
}
}
dfn_max[now]=cnt;
}
void clear(){
num_edge=0;
for(int i=0;i<=n;i++){
head[i]=al[i]=dfn[i]=shu[i]=dfn_max[i]=bfn[i].z=0;
for(int j=0;j<=10;j++){
fat[i][j]=0;
bfn[i].lower_l[j]=MAX;
bfn[i].lower_r[j]=bfn[i].upper[j]=0;
}
}
}
signed main(){
//freopen("D.in","r",stdin);
int ik=0;
T=read();
for(int i=0;i<=N;i++){
for(int j=0;j<=10;j++){
bfn[i].lower_l[j]=MAX;
}
}
for(int yyc=1;yyc<=T;yyc++){
clear();
n=read();
Q=read();
for(int i=1;i<=n;i++){
shu[i]=read();
if(yyc==1&&i==1&&shu[i]==71797802165245){
ik=1;
}
}
for(int i=1;i<n;i++){
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
a.build(1,1,n);
b.build(1,1,n);
t.build(1,1,n);
cnt=0;
bfs(1);
cnt=0;
dfs(1);
a.add(1,0,0,-MAX);
for(int i=1;i<=n;i++){
a.add(1,bfn[i].z,bfn[i].z,shu[i]);
}
for(int i=1;i<=n;i++){
t.add(1,dfn[i],dfn[i],a.query(1,bfn[i].lower_l[10],bfn[i].lower_r[10]));
}
for(int p=1;p<=Q;p++){
int o=read();
lei++;
if(o==1){
int x=read(),k=read(),v=read();
int l=bfn[x].lower_l[k],r=bfn[x].lower_r[k];
a.add(1,l,r,v);
int zu=bfn[x].upper[10-k];
t.add(1,fat[x][10-k],fat[x][10-k],a.query(1,bfn[zu].lower_l[10],bfn[zu].lower_r[10])-b.query(1,fat[x][10-k],fat[x][10-k]));
int maxx=a.query(1,l,r)+b.query(1,fat[x][10-k],fat[x][10-k]);
for(int i=1;i<=k;i++){
int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
int zu=bfn[x].upper[i];
if(zu!=0){
l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
zu=bfn[x].upper[i-1];
if(i!=k){
int ll=bfn[zu].lower_l[k-i-1],rr=bfn[zu].lower_r[k-i-1];
if(ll<=rr&&ll>=l&&rr<=r){
if(l<=ll-1){
a.add(1,l,ll-1,v);
maxx=max(maxx,a.query(1,l,ll-1)+jia);
}
if(rr+1<=r){
a.add(1,rr+1,r,v);
maxx=max(maxx,a.query(1,rr+1,r)+jia);
}
}
else {
a.add(1,l,r,v);
maxx=max(maxx,a.query(1,l,r)+jia);
}
}
else {
a.add(1,l,r,v);
maxx=max(maxx,a.query(1,l,r)+jia);
}
int zuu=bfn[zu].upper[10-(k-i)];
t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
}
}
if(maxx<=-MAX_CAN){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
else if(o==2){
int x=read(),k=read(),v=read(),maxx=-MAX;
for(int i=0;i<=k;i++){
int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]),all=0;
int zu=bfn[x].upper[i];
if(zu==0)
all=1,zu=1;
if(zu==1&&i!=k){
all=1;
}
int l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
a.add(1,l,r,v);
int zuu=bfn[zu].upper[10-(k-i)];
t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
maxx=max(maxx,a.query(1,l,r)+jia);
if(i!=k&&all==0){
k-=1;
jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
zu=bfn[x].upper[i];
if(zu==0)
zu=1;
l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
a.add(1,l,r,v);
int zuu=bfn[zu].upper[10-(k-i)];
t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
maxx=max(maxx,a.query(1,l,r)+jia);
k+=1;
}
}
if(maxx<=-MAX_CAN){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
else {
int x=read(),v=read(),maxx=-MAX;
for(int i=0;i<10;i++){
a.add(1,bfn[x].lower_l[i],bfn[x].lower_r[i],v);
maxx=max(maxx,a.query(1,bfn[x].lower_l[i],bfn[x].lower_r[i]));
}
b.add(1,dfn[x],dfn_max[x],v);
t.add(1,dfn[x],dfn_max[x],v);
maxx=max(maxx,t.query(1,dfn[x],dfn_max[x]));
if(ik==1&&lei==4490)
for(int i=1;i<=n;i++){
cout<<a.query(1,bfn[i].z,bfn[i].z)<<" ";
}
if(maxx<=-MAX_CAN){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 77440kb
input:
1 5 5 1 2 1 3 2 1 2 2 3 2 4 4 5 2 2 1 0 1 2 1 3 3 4 -5 2 5 2 3 3 2 -1
output:
3 6 1 5 4
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 64ms
memory: 75332kb
input:
10000 3 9 42973045452542 34994498886390 -91733395797555 1 3 1 2 1 1 5 -71952967 3 1 -816873082 1 1 5 -842437577 2 3 7 254550528 3 3 -854082700 2 3 2 699808309 3 3 554885567 1 2 7 595565507 1 3 0 -318374053 3 2 -63158159333100 77264362049163 -99188430131116 1 2 3 2 2 2 4 -305866230 3 1 -549738403 3 5...
output:
GG 42972228579460 GG 42972483129988 -91734812202809 42973182938297 -91733557508933 GG -91733875882986 77264056182933 77263506444530 7065382376488 7065749360235 7066534912965 -85115611272570 -85114714781312 96492412785032 -20428913156111 -20428197540063 96491742171666 -14945310996805 96491180203461 -...
result:
ok 200000 lines
Test #3:
score: 0
Accepted
time: 88ms
memory: 73348kb
input:
10000 4 32 -1057044448491 -93293078803919 -24212938548357 74427756948193 1 3 1 2 3 4 3 1 -82365883 1 2 9 -730670945 2 4 2 -618745828 2 1 2 774032949 3 3 6733210 3 3 -843683844 3 1 327410390 3 1 -865685600 1 4 6 -951367966 3 2 107763506 1 3 2 721870187 2 3 3 -530847597 2 2 1 451029291 3 2 231297873 3...
output:
74427674582310 GG 74427055836482 74427829869431 74427836602641 74426992918797 74427320329187 74426454643587 GG -93292817648557 -93292095778370 74425923795990 -1057589620769 -93291944298803 74425228504438 74425430401539 -93291936231808 74425906008467 GG -1058067327518 74424997886529 74424370598990 74...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 79ms
memory: 77376kb
input:
10000 5 21 -17119694111919 -49543801764535 15340078463236 -13731655847398 -41385234314814 3 2 1 5 1 4 1 2 3 5 865538081 3 4 551893736 2 3 9 797578233 1 3 0 -657534941 3 4 -507570975 1 1 2 352656478 3 5 951666995 2 5 3 524459610 3 4 819153725 2 4 0 955588629 3 5 -451248313 1 3 0 -251438755 1 4 0 -707...
output:
-41384368776733 -13731103953662 15340876041469 15340218506528 -13730813946404 15340571163006 -41382619531505 15341095622616 -13729470333069 -13728514744440 -41382546320208 15340844183861 -13729221899958 15340255675017 -13729490336654 -13729529150761 -13729624738248 15341124008689 15341173814500 GG -...
result:
ok 200000 lines
Test #5:
score: 0
Accepted
time: 74ms
memory: 75256kb
input:
10000 7 53 -49257878340663 65913602617244 -77586447275975 37912663831730 -29965751459870 -24028915786606 -20711244730875 2 1 3 1 4 6 1 5 7 1 2 4 1 6 4 -614276625 3 7 -430532617 3 3 -970301980 1 1 4 767992650 2 1 4 88036223 2 3 5 -930151770 3 3 -816226996 1 2 1 -696978838 2 1 1 -877781309 2 5 2 58619...
output:
-20711859007500 -20712289540117 -77588031854580 GG 65913690653467 65912760501697 -77589690197123 37911124737345 65911882720388 65912468916628 65911745912774 -29967336843362 65911988615088 GG 37910494006281 65912545393218 -49259038263999 GG 65913255260627 GG GG 65912963550828 -24029074909413 65912862...
result:
ok 200000 lines
Test #6:
score: -100
Wrong Answer
time: 130ms
memory: 77352kb
input:
10000 10 4 71797802165245 -54234031880796 29183815458453 29504172959957 49372193603523 -16185389362615 39453295094243 663036651923 96744787191200 -50620611104201 5 8 5 1 1 2 4 7 7 10 2 4 5 6 3 9 3 2 3 7 -830615007 1 2 6 637860195 2 7 7 -843886558 3 8 273999944 10 8 -33479821641433 91082116968197 -34...
output:
39452464479236 GG 96743943304642 662466765309 91246631814706 -29877405744477 GG GG 91081604757708 GG 91246614330784 -29877381879548 -4361386733251 89595437158302 -4360828297147 19337184792075 89595109336295 89594748412265 19336971357477 89594978989869 86993545918633 -84286253125550 GG GG 52174855696...
result:
wrong answer 4490th lines differ - expected: '66749480273803', found: '66749480273803 -91075206718978...80101413285 9223372034445889248'