QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#758108 | #9373. Query on Tree | Larunatrecy | ML | 0ms | 18484kb | C++14 | 4.3kb | 2024-11-17 15:52:23 | 2024-11-17 15:52:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
x=(f?-x:x);
}
typedef long long LL;
const int N = 2e5+7;
int n,m;
LL a[N];
vector<int> G[N];
LL mx[N<<2],tag[N<<2];
void pushup(int k)
{
mx[k]=max(mx[k<<1],mx[k<<1|1]);
}
void pushtag(int k,LL v)
{
mx[k]+=v;
tag[k]+=v;
}
void pushdown(int k)
{
if(tag[k])
{
pushtag(k<<1,tag[k]);
pushtag(k<<1|1,tag[k]);
tag[k]=0;
}
}
int dfn[N],seq[N];
void build(int k,int l,int r)
{
tag[k]=0;
if(l==r)
{
mx[k]=a[seq[l]];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int l,int r,int L,int R,LL v)
{
if(L<=l&&r<=R)
{
pushtag(k,v);
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L<=mid)modify(k<<1,l,mid,L,R,v);
if(R>mid)modify(k<<1|1,mid+1,r,L,R,v);
pushup(k);
}
LL query(int k,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return mx[k];
pushdown(k);
LL res=-1e18;
int mid=(l+r)>>1;
if(L<=mid)res=max(res,query(k<<1,l,mid,L,R));
if(R>mid)res=max(res,query(k<<1|1,mid+1,r,L,R));
return res;
}
LL calc(LL l,LL r,LL v)
{
if(l>r)return -1e18;
// cout<<l<<' '<<r<<' '<<v<<endl;
modify(1,1,n,l,r,v);
return query(1,1,n,l,r);
}
int tot=0,fa[N];
int ls[N][11],rs[N][11],dep[N];
void dfs(int x,int pre)
{
fa[x]=pre;
queue<int> q;
q.push(x);
while(!q.empty())
{
int u=q.front();
q.pop();
if(!dfn[u])seq[dfn[u]=++tot]=u;
int d=dep[u]-dep[x];
ls[x][d]=min(ls[x][d],dfn[u]);
rs[x][d]=max(rs[x][d],dfn[u]);
if(dep[u]-dep[x]==10)continue;
for(int v:G[u])if(v!=fa[u])
{
q.push(v);
}
}
ls[x][10]=tot+1;
for(int y:G[x])if(y!=fa[x])
dfs(y,x);
rs[x][10]=tot;
}
void dfs1(int x,int pre)
{
fa[x]=pre;dep[x]=dep[pre]+1;
for(int y:G[x])if(y!=pre)
dfs1(y,x);
}
void solve()
{
tot=0;int tid;
read(n);read(m);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<n;i++)
{
int u,v;
read(u);read(v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=10;j++)
ls[i][j]=n+1,rs[i][j]=0;
dfs1(1,0);dfs(1,0);
build(1,1,n);
while(m--)
{
LL op,x,k,v;
read(op);
if(op==1)
{
read(x);read(k);read(v);
int y=0;
LL res=-1e18;
for(int i=0;i<=k;i++)
{
if(!x)break;
int d=k-i;
if(d==0||y==0||ls[y][d-1]>rs[y][d-1])
res=max(res,calc(ls[x][d],rs[x][d],v));
else
{
res=max(res,calc(ls[x][d],ls[y][d-1]-1,v));
res=max(res,calc(rs[y][d-1]+1,rs[x][d],v));
}
y=x;x=fa[x];
}
if(res==-1e18)printf("GG\n");
else printf("%lld\n",res);
}
else if(op==2)
{
read(x);read(k);read(v);
LL res=-1e18;
for(int i=0;i<=k;i++)
{
if(!x)x=1;
res=max(res,calc(ls[x][k-i],rs[x][k-i],v));
x=fa[x];
}
if(res==-1e18)printf("GG\n");
else printf("%lld\n",res);
}
else
{
read(x);read(v);
LL res=-1e18;
for(int i=0;i<=10;i++)
res=max(res,calc(ls[x][i],rs[x][i],v));
if(res==-1e18)printf("GG\n");
else printf("%lld\n",res);
}
}
}
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int t;
read(t);
while(t--)
{
solve();
}
return 0;
}
/*
2
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
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18484kb
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: -100
Memory Limit Exceeded
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...