QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586710 | #9373. Query on Tree | bessie_goes_moo | WA | 91ms | 75272kb | C++14 | 10.1kb | 2024-09-24 15:09:31 | 2024-09-24 15:09:31 |
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=1;
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();
if(yyc==1&&n==3){
ik=0;
}
Q=read();
for(int i=1;i<=n;i++){
shu[i]=read();
}
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(lei==234&&ik==1){
cout<<n<<" "<<o<<" ";
}
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(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);
}
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(maxx<=-MAX_CAN){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
// for(int i=1;i<=n;i++){
// cout<<a.query(1,bfn[i].z,bfn[i].z)<<" ";
// }
// cout<<endl;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 75272kb
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: 91ms
memory: 73340kb
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: -100
Wrong Answer
time: 80ms
memory: 75272kb
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:
wrong answer 234th lines differ - expected: '-78585193822704', found: '4 1 97686244528495'