QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#758108#9373. Query on TreeLarunatrecyML 0ms18484kbC++144.3kb2024-11-17 15:52:232024-11-17 15:52:24

Judging History

你现在查看的是最新测评结果

  • [2024-11-17 15:52:24]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:18484kb
  • [2024-11-17 15:52:23]
  • 提交

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...

output:


result: