QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#598723#9373. Query on TreefutarianRE 0ms0kbC++118.0kb2024-09-28 23:08:452024-09-28 23:08:49

Judging History

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

  • [2024-09-28 23:08:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-28 23:08:45]
  • 提交

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

output:


result: