#C241010B. 旅游

标签（Label）

• 点分树

网址（Website）

题目详情 - 旅游 - Super

题解 - 旅游 - Super

题解（Solution）

自己想出来的！！！

其他的和模板差不多，用一个 $\verb!set!$ 维护保护点的权值，再用一个 $f_i$ 维护以点 $i$ 的子树节点走到点 $i$ 时的权值最大值，则有 $f_i=\max\{a_i+lst_i-dis(i,x)\}$ ，其中 $lst_i$ 表示上次修改的时间，则最后的答案就是 $\max\{a_i+lst_i-t-dis(i,x)\}$ ，相当于每次在点分树上跳父节点 $i$ ，计算 $\max\{f_i-dis(i,x)\}$ ，考虑会不会出现路径算重的情况，发现如果路径重合，那么两个点一定在子树中就计算过了且在子树中计算的一定更优秀，因此可以不管。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 201234;
bool ST;

int n,q,a[N],lst[N];
vector<int> ft[N];

struct LCA{
	int f[N][24],dfn[N],idx;
	int dep[N];
	void dfs(int x,int F){
		f[dfn[x]=++idx][0] = F, dep[x] = dep[F]+1;
		for(int y:ft[x]) if(y^F) dfs(y,x);
	}
	inline int cmn(int x,int y){return dfn[x]<dfn[y]?x:y;}
	inline int lca(int x,int y){
		if(x==y) return x;
		if((x=dfn[x])>(y=dfn[y])) swap(x,y);
		int d = __lg(y-x++);
		return cmn(f[x][d], f[y-(1<<d)+1][d]);
	}inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
	void init(){
		dfs(1,0);
		For(j,1,18) for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j] = cmn(f[i][j-1], f[i+(1<<(j-1))][j-1]);
	}
}G;

struct Point_Tree{
	int siz[N],mx,rt;
	bitset<N> vst;
	void dfs_root(int x,int F,int sum){
		siz[x] = 1;int sub = 0;
		for(auto y:ft[x]) if(y^F && !vst[y]) 
			dfs_root(y,x,sum),siz[x]+=siz[y],sub=max(sub,siz[y]);
		sub = max(sub, sum-siz[x]);
		if(sub<mx) mx=sub, rt=x;
	}
	int fa[N];
	void devide(int x,int sum){
		vst[x] = true;
		for(auto y:ft[x]) if(!vst[y]){
			siz[y] = siz[x]>siz[y] ? siz[y] : (sum-siz[x]);
			rt=0,mx=N,dfs_root(y,x,siz[y]),fa[rt]=x,devide(rt,siz[y]);
		}
	}void init(){mx=N,rt=0,dfs_root(1,0,n),devide(rt,n);}
	int f[N];
	void update(int x,int k){for(int i=x;i;i=fa[i]) f[i] = max(f[i], k-G.dis(x,i));}
	int ask(int x){
		int res = -inf;
		for(int i=x;i;i=fa[i]) res = max(res, f[i]-G.dis(x,i));
		return res;
	}
}T;

set<P> s;//用s来维护所有固定点的信息
void Solve(){
	n=rd(),q=rd();For(i,1,n) a[i]=rd();
	For(i,1,n-1){
		int x=rd(),y=rd();
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}T.init(), G.init(), s.insert({0,0});
	For(i,1,n) T.update(i,a[i]);
	while(q--){
		int opt=rd(),t=rd(),x=rd();
		if(opt==1){
			a[x] -= t-lst[x], lst[x] = t;
			s.insert({a[x],x});
		}else 
		if(opt==2){
			s.erase({a[x],x});
			lst[x] = t;
			T.update(x,a[x]+lst[x]);
		}else{
			int ans = s.rbegin()->x;
			ans = max(ans, T.ask(x)-t);
			printf("%d\n", ans);
		} 
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}