#C241121B. [国家集训队] 旅游

树链剖分
题目
发布日期:   2024-11-21
更新日期:   2024-11-21
文章字数:   1.7k
阅读时长:   8 分

#C241121B. [国家集训队] 旅游

标签（Label）

  • 树链剖分

网址（Website）

P1505 [国家集训队] 旅游 - 洛谷

题目（Problem）

题目背景

Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有 $n$ 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有 $n-1$ 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 $w$，也就是说，Ray 经过这座桥会增加 $w$ 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 $u$ 景点到 $v$ 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

题目描述

给定一棵 $n$ 个节点的树，边带权，编号 $0 \sim n-1$，需要支持五种操作：

  • C i w 将输入的第 $i$ 条边权值改为 $w$；
  • N u v 将 $u,v$ 节点之间的边权都变为相反数；
  • SUM u v 询问 $u,v$ 节点之间边权和；
  • MAX u v 询问 $u,v$ 节点之间边权最大值；
  • MIN u v 询问 $u,v$ 节点之间边权最小值。

保证任意时刻所有边的权值都在 $[-1000,1000]$ 内。

输入格式

第一行一个正整数 $n$，表示节点个数。
接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边，描述这棵树。
然后一行一个正整数 $m$，表示操作数。
接下来 $m$ 行，每行表示一个操作。

输出格式

对于每一个询问操作，输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

样例输出 #1

3
2
1
-1
5
3

提示

【数据范围】

对于 $100%$ 的数据，$1\le n,m \le 2\times 10^5$。

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving

题解（Solution）

非常简单的树链剖分板子，直接下放边权到点上，然后就是板子了。

主要考验代码能力。

时间复杂度 $O(n\log^2 n)$ 。

结果最后发现我的 dfs_top 没有 top[x]=tp 这一句，导致我调了好久。

代码（Code）

100分
#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--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n';
using namespace std;
#define P pair<int,int> 
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
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;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}const int inf = 0x3f3f3f3f;
const int N = 1012345;
bool ST;
double Tim,TT;

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

int son[N],siz[N],dep[N],fa[N];
void dfs_siz(int x,int F,int w){
	dep[x] = dep[fa[x]=F]+1, siz[x]=1, a[x]=w;
	for(auto p:ft[x]) if(p.x^F){
		dfs_siz(p.x,x,p.y);
		siz[x] += siz[p.x];
		son[x] = siz[son[x]] >= siz[p.x] ? son[x] : p.x;
	}
}

int top[N],id[N],w[N],idx;
void dfs_top(int x,int tp){
	id[x] = ++idx, w[idx]=a[x], top[x]=tp;
	if(!son[x]) return;
	dfs_top(son[x], tp);
	for(auto p:ft[x])
		if(p.x^son[x] && p.x^fa[x]) dfs_top(p.x,p.x);
}

namespace T{
	#define mid ((l+r)>>1)
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Tr{int min,max,sum,rev;}tr[N<<2|3];
	inline void pushup(Tr &t,Tr l,Tr r){t = {min(l.min,r.min), max(l.max,r.max), l.sum+r.sum};}
	void build(int p,int l,int r){
		tr[p]={w[l],w[l],w[l],0};
		if(l==r) return;
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(tr[p],tr[ls],tr[rs]);
	}
	inline void pushtag(int p){
		swap(tr[p].max, tr[p].min);
		tr[p].max=-tr[p].max;
		tr[p].min=-tr[p].min;
		tr[p].sum=-tr[p].sum;
		tr[p].rev^=1;
	}
	inline void pushdown(int p){
		if(tr[p].rev){
			pushtag(ls), pushtag(rs);
			tr[p].rev = 0;
		} 
	}
	void update(int p,int l,int r,int pos,int val){
		if(l==r) return tr[p] = {val,val,val}, void();
		if(l^r) pushdown(p);
		if(pos<=mid) update(ls,l,mid,pos,val);
		else update(rs,mid+1,r,pos,val);
		pushup(tr[p],tr[ls],tr[rs]);
	}
	void update_edge(int x,int y,int w){
		if(dep[x] < dep[y]) swap(x,y);
		update(1,1,n,id[x],w);
	}
	void modify(int p,int l,int r,int L,int R){
		if(L<=l && r<=R) return pushtag(p);
		if(l^r) pushdown(p);
		if(L<=mid) modify(ls,l,mid,L,R);
		if(R>mid) modify(rs,mid+1,r,L,R);
		pushup(tr[p],tr[ls],tr[rs]);
	}
	Tr ask(int p,int l,int r,int L,int R){
		if(L<=l && r<=R) return tr[p];if(l^r) pushdown(p);
		if(R<=mid) return ask(ls,l,mid,L,R);
		if(L>mid) return ask(rs,mid+1,r,L,R);
		Tr T;return pushup(T,ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R)),T;
	}
	void update_path(int x,int y){
		while(top[x]^top[y]){
			if(dep[top[x]] < dep[top[y]]) swap(x,y);
			modify(1,1,n,id[top[x]], id[x]);
			x = fa[top[x]];
		}
		if(dep[x] < dep[y]) swap(x,y);
		if(x^y) modify(1,1,n,id[y]+1,id[x]);//防止出错 
	}
	Tr ask(int x,int y){
		Tr res = {inf,-inf,0};
		while(top[x]^top[y]){
			if(dep[top[x]] < dep[top[y]]) swap(x,y);
			pushup(res, res, ask(1,1,n,id[top[x]],id[x]));
			x=fa[top[x]];
		}
		if(dep[x] < dep[y]) swap(x,y);
		if(x^y) pushup(res, res, ask(1,1,n,id[y]+1,id[x]));
		return res;
	}
}

void Solve(){
	n=rd();For(i,1,n-1){
		int x=rd()+1,y=rd()+1,w=rd();
		q[i] = {x,y};
		ft[x].emplace_back(y,w);
		ft[y].emplace_back(x,w);
	}
	
	dfs_siz(1,0,0);
	dfs_top(1,0);
	T::build(1,1,n);
	
	m=rd();
	while(m--){
		string s;cin>>s;int x=rd()+1,y=rd()+1;
		if(s[0]=='C') x--,y--,T::update_edge(q[x].x,q[x].y,y);
		if(s[0]=='N') T::update_path(x,y);
		if(s[0]=='S') write(T::ask(x,y).sum), putchar('\n');
		if(s[1]=='A') write(T::ask(x,y).max), putchar('\n');
		if(s[1]=='I') write(T::ask(x,y).min), putchar('\n');
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int Tt=1;Tim = clock();while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2024/11/21/C241121B-%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F-%E6%97%85%E6%B8%B8/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
树链剖分
赏
  目录