QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#598723 | #9373. Query on Tree | futarian | RE | 0ms | 0kb | C++11 | 8.0kb | 2024-09-28 23:08:45 | 2024-09-28 23:08:49 |
answer
//母亲?懂?
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ll long long
const int Len = 2e5 + 15 , Inf = 1e14;
int mxdep,dep[Len],N,n,q,id,siz[Len],nfd[Len],nfb[Len],dfn[Len],bfn[Len],fa[11][Len],a[Len],b[Len],t[Len],head[Len],cnt,L[11][Len],R[11][Len];
struct node
{
int next,to;
}edge[Len << 1];
inline void add(int from,int to)
{
edge[++ cnt].to = to;
edge[cnt].next = head[from];
head[from] = cnt;
}
inline int read()
{
char ch = getchar();
int x = 0 , f = 1;
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while('0' <= ch && ch <= '9')
{
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * f;
}
void write(ll x)
{
if(x < 0){putchar('-');x = -x;}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline void writeN(ll x){write(x) , putchar('\n');}
void dfs(int x,int f)
{
siz[x] = 1;
if(x == 1) dep[x] = 11;
else dep[x] = dep[f] + 1;
dfn[x] = ++ id;nfd[id] = x;
mxdep = max(mxdep , dep[x]);
fa[0][x] = x;L[0][x] = R[0][x] = bfn[x];
if(x == 1)
{
int now = 0;
for(int i = 1 ; i <= 10 ; i ++)
{
now = fa[i][x] = n + i;
//printf("%d %d %d\n",i,x,fa[i][x]);
L[i][now] = R[i][now] = 1;
}
}
else
{
int now = 0;
for(int i = 1 ; i <= 10 ; i ++)
{
now = fa[i][x] = fa[i - 1][f];
//printf("%d %d %d\n",i,x,fa[i][x]);
L[i][now] = min(L[i][now] , bfn[x]) , R[i][now] = max(R[i][now] , bfn[x]);
}
}
for(int e = head[x] ; e ; e = edge[e].next)
{
int to = edge[e].to;
if(to == f) continue;
dfs(to , x);
siz[x] += siz[to];
}
}
void bfs()
{
queue<int> Q;
Q.push(1);
while(!Q.empty())
{
int p = Q.front();Q.pop();
bfn[p] = ++ id;nfb[p] = id;
for(int e = head[p] ; e ; e = edge[e].next)
{
int to = edge[e].to;
if(!bfn[to]) Q.push(to);
}
}
}
//Sub 1:树状数组维护路径和,区间加,单点查
int treec[Len];
#define lowbit(x) (x & (-x))
inline void Add(int x,int d)
{
while(x <= n)
{
treec[x] += d;
x += lowbit(x);
}
}
inline void Upd(int l,int r,int w){Add(l , w) , Add(r + 1 , -w);}
inline int qry(int x)
{
int res = 0;
while(x)
{
res += treec[x];
x -= lowbit(x);
}
return res;
}
//Sub 2:线段树维护 bfs 序上的 max A,操作:区间加区间 max
//Sub3:线段树维护 dfs 序上的 b_o + t_o + roadsum,涉及区间加区间 max 单点改
struct Seg
{
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int mx[Len << 2],tag[Len << 2];
inline void push_up(int p){mx[p] = max(mx[ls(p)] , mx[rs(p)]);}
inline void push_down(int p)
{
if(tag[p])
{
tag[ls(p)] += tag[p] , tag[rs(p)] += tag[p];
mx[ls(p)] += tag[p] , mx[rs(p)] += tag[p];
tag[p] = 0;
}
}
void build(int p,int l,int r)
{
tag[p] = 0;
if(l == r){mx[p] = a[nfb[l]];return;}
int mid = (l + r) >> 1;
build(ls(p) , l , mid) , build(rs(p) , mid + 1 , r);
push_up(p);
}
void Build(int p,int l,int r)
{
tag[p] = 0;
if(l == r){mx[p] = b[nfd[l]];return;}
int mid = (l + r) >> 1;
Build(ls(p) , l , mid) , Build(rs(p) , mid + 1 , r);
push_up(p);
}
void updP(int p,int l,int r,int idx,int w)
{
if(l == r){mx[p] = w;return;}
push_down(p);
int mid = (l + r) >> 1;
if(idx <= mid) updP(ls(p) , l , mid , idx , w);
else updP(rs(p) , mid + 1 , r , idx , w);
push_up(p);
}
void update(int p,int l,int r,int nl,int nr,int w)
{
if(nl <= l && nr >= r)
{
mx[p] += w;
tag[p] += w;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(nl <= mid) update(ls(p) , l , mid , nl , nr , w);
if(nr > mid) update(rs(p) , mid + 1 , r , nl , nr , w);
push_up(p);
}
int query(int p,int l,int r,int nl,int nr)
{
if(nl <= l && nr >= r) return mx[p];
push_down(p);
int mid = (l + r) >> 1 , res = -Inf;
if(nl <= mid) res = max(res , query(ls(p) , l , mid , nl , nr));
if(nr > mid) res = max(res , query(rs(p) , mid + 1 , r , nl , nr));
return res;
}
}S2,S3;
struct Sec
{
int l,r;
Sec(){l = r = 0;}
Sec(int L,int R){l = L , r = R;}
}rnm[Len];int rtf[Len];
signed main()
{
int T = read();
while(T --)
{
N = n = read() , q = read();
for(int i = 1 ; i <= n ; i ++) a[i] = read();
for(int i = 1 ; i < n ; i ++)
{
int x = read() , y = read();
add(x , y) , add(y , x);
}
for(int i = n + 2 ; i <= n + 10 ; i ++) add(i , i - 1);add(n + 1 , 1);
N = n + 10;
for(int i = n + 1 ; i <= n + 9 ; i ++) fa[1][i] = i + 1;
for(int i = 1 ; i <= N ; i ++) for(int j = 0 ; j <= 10 ; j ++) for(int j = 1 ; j <= 10 ; j ++) L[j][i] = n + 1 , R[j][i] = 0;
bfs();id = 0;
dfs(1 , 0);//puts("#bfs");for(int i = 1 ; i <= n ; i ++) printf("%d ",bfn[i]);puts("");
S2.build(1 , 1 , n);
for(int i = 1 ; i <= n ; i ++)
{
t[i] = 0;
if(L[10][i] > R[10][i]) b[i] = -Inf;
else b[i] = S2.query(1 , 1 , n , L[10][i] , R[10][i]);
}
S3.Build(1 , 1 , n);
for(int i = 1 ; i <= q ; i ++)
{
int o = read(),x = read(),k,v;
if(o == 1 || o == 2) k = read();
v = read();
if(o == 1)
{
int op = k , ff = fa[10 - k][x] , now = x , res = -Inf;
S2.update(1 , 1 , n , L[k][now] , R[k][now] , v);res = max(res , S2.query(1 , 1 , n , L[k][now] , R[k][now]) + qry(dfn[fa[1][ff]]));
b[ff] = S2.query(1 , 1 , n , L[10][ff] , R[10][ff]);
S3.updP(1 , 1 , n , dfn[ff] , b[ff] + qry(dfn[fa[1][ff]]));
k --;
now = fa[1][now] , ff = fa[1][ff];
while(k > 1 && now <= n)
{
S2.update(1 , 1 , n , L[k][now] , L[k - 1][x] - 1 , v);res = max(res , S2.query(1 , 1 , n , L[k][now] , L[k - 1][x] - 1) + qry(dfn[fa[1][ff]]));
S2.update(1 , 1 , n , R[k - 1][x] + 1 , R[k][now] , v);res = max(res , S2.query(1 , 1 , n , R[k - 1][x] + 1 , R[k][now]) + qry(dfn[fa[1][ff]]));
b[ff] = S2.query(1 , 1 , n , L[10][ff] , R[10][ff]);
S3.updP(1 , 1 , n , dfn[ff] , b[ff] + qry(dfn[fa[1][ff]]));
k --;
now = fa[1][now] , ff = fa[1][ff];
}
if(!k && now <= n)
{
S2.update(1 , 1 , n , L[k][now] , R[k][now] , v);res = max(res , S2.query(1 , 1 , n , L[k][now] , L[k - 1][x] - 1) + qry(dfn[fa[1][ff]]));
b[ff] = S2.query(1 , 1 , n , L[10][ff] , R[10][ff]);
S3.updP(1 , 1 , n , dfn[ff] , b[ff] + qry(dfn[fa[1][ff]]));
}
writeN(res);
}
else if(o == 2)
{
int res = -Inf , mxdp = dep[x] + k , mndp = dep[x] - k , tf = fa[10 - k][x];
for(int j = mxdp ; j >= mndp ; j --)
{
rnm[j].l = n + 1 , rnm[j].r = 0;
rtf[j] = tf;
tf = fa[1][tf];
}
//puts("#1");
int K = k , now = x , nb = 0;
while(K >= 0 && now <= n)
{
for(int j = 0 ; j <= K ; j ++)
{
nb = dep[now] + j;
rnm[nb].l = min(rnm[nb].l , L[j][now]) , rnm[nb].r = max(rnm[nb].r , R[j][now]);
}
K --;
now = fa[1][now];
}
//puts("#2");
for(int j = mndp ; j <= mxdp ; j ++)
{
// printf("%d %d %d %d %d %d\n",j,rnm[j].l,rnm[j].r,rtf[j],L[10][rtf[j]] , R[10][rtf[j]]);
S2.update(1 , 1 , n , rnm[j].l , rnm[j].r , v);
b[rtf[j]] = S2.query(1 , 1 , n , L[10][rtf[j]] , R[10][rtf[j]]);
S3.updP(1 , 1 , n , dfn[rtf[j]] , b[rtf[j]] + qry(dfn[fa[1][rtf[j]]]));
res = max(res , S2.query(1 , 1 , n , rnm[j].l , rnm[j].r) + qry(dfn[fa[1][rtf[j]]]));
}
//puts("#3");
writeN(res);
}
else if(o == 3)
{
int K = 9 , res = -Inf;
for(k = 0 ; k <= K ; k ++)
{
int ff = fa[10 - k][x];
S2.update(1 , 1 , n , L[k][x] , R[k][x] , v);
b[ff] = S2.query(1 , 1 , n , L[10][ff] , R[10][ff]);
S3.updP(1 , 1 , n , dfn[ff] , b[ff] + qry(dfn[fa[1][ff]]));
res = max(res , S2.query(1 , 1 , n , L[k][x] , R[k][x]) + qry(dfn[fa[1][ff]]));
}
Upd(dfn[x] , dfn[x] + siz[x] - 1 , v);
S3.update(1 , 1 , n , dfn[x] , dfn[x] + siz[x] - 1 , v);
res = max(res , S3.query(1 , 1 , n , dfn[x] , dfn[x] + siz[x] - 1));
writeN(res);
}
}
mxdep = cnt = id = 0;
for(int i = 1 ; i <= n ; i ++) nfd[i] = nfb[i] = dfn[i] = bfn[i] = head[i] = 0;
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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