xiaoMa
"Bye Bye Baby Blue"
P1501,ZJOI-2012(LCT)

P1501 [国家集训队]Tree II

题目描述

一棵 $N$个点的树,每个点的初始权值为 $1$。
对于这棵树有 $q$ 个操作,每个操作为以下四种操作之一:

  • + u v c:将 $u$到 $v$ 的路径上的点的权值都加上自然数 $c$;
  • - u1 v1 u2 v2:将树中原有的边 $(u_1,v_1)$ 删除,加入一条新边 $(u_2,v_2)$,保证操作完之后仍然是一棵树;
  • * u v c:将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$;
  • / u v:询问 $u$ 到 $v$ 的路径上的点的权值和,将答案对 5106151061 取模。

输入格式

第一行两个整数 $n$,$q$

接下来 $n-1$ 行每行两个正整数 $u$,$v$,描述这棵树的每条边。

接下来 $q$行,每行描述一个操作。

带修的LCT, 类似于线段树放一下懒标记就行了

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using uint = unsigned int ;
using namespace std ;
const int N = 1e5 + 5 ;
const int Mod = 51061 ;
uint n , q , fa[N] , ch[N][2] , val[N] , sum[N] , sz[N] , mul[N] , add[N] ;
bool rev[N] ;
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
inline void Add(uint &amp; x , uint y) { x += y ; x %= Mod ; }
inline void Mul(uint &amp; x , uint y) { x *= y ; x %= Mod ; }
inline bool isroot(uint x) { return (ls(fa[x]) != x) &amp;&amp; (rs(fa[x]) != x) ; }
inline void pushup(uint x) { sum[x] = (sum[ls(x)] + sum[rs(x)] + val[x]) ; sum[x] %= Mod ; sz[x] = (sz[ls(x)] + sz[rs(x)] + 1) ; }
inline void pushr(uint x) { swap(ls(x) , rs(x)) ; rev[x] ^= 1 ; }
inline void pushm(uint x , uint v) { Mul(sum[x] , v) ; Mul(val[x] , v) ; Mul(mul[x] , v) ; Mul(add[x] , v) ; }
inline void pusha(uint x , uint v) { Add(sum[x] , v * sz[x]) ; Add(val[x] , v) ; Add(add[x] , v) ; }
inline void pushdown(uint x) {
  if(mul[x] != 1) { pushm(ls(x) , mul[x]) ; pushm(rs(x) , mul[x]) ; mul[x] = 1 ; }
  if(add[x]) { pusha(ls(x) , add[x]) ; pusha(rs(x) , add[x]) ; add[x] = 0 ; }
  if(rev[x]) { if(ls(x)) pushr(ls(x)) ; if(rs(x)) pushr(rs(x)) ; rev[x] = 0 ; }
}
inline bool getr(uint x) { return rs(fa[x]) == x ; }
inline void rotate(uint x) { uint y = fa[x] , z = fa[y] , k = getr(x) , w = ch[x][k ^ 1] ;
  if(! isroot(y)) ch[z][getr(y)] = x ;
  ch[x][k ^ 1] = y ; ch[y][k] = w ;
  if(w) fa[w] = y ; fa[y] = x ; fa[x] = z ;
  pushup(y) ;
}
inline void pushall(uint x) { if(! isroot(x)) pushall(fa[x]) ; pushdown(x) ; }
inline void splay(uint x) { pushall(x) ;
  while(! isroot(x)) { uint y = fa[x] ;
    if(! isroot(y)) { rotate(getr(y) ^ getr(x) ? x : y) ; }
    rotate(x) ;
  } pushup(x) ;
}
inline void access(uint x) { for(uint tp = 0 ; x ; tp = x , x = fa[tp]) splay(x) , rs(x) = tp , pushup(x) ; }
inline void makeroot(uint x) { access(x) ; splay(x) ; pushr(x) ; }
inline void split(uint x , uint y) { makeroot(x) ; access(y) ; splay(y) ; }
inline void link(uint x , uint y) { makeroot(x) ; fa[x] = y ; }
inline void cut(uint x , uint y) { split(x , y) ; fa[x] = ls(y) = 0 ; }
signed main() {
  ios :: sync_with_stdio(false) ;
  cin.tie(nullptr) ;
  cout.tie(nullptr) ;
  cin >> n >> q ;
  for(register int i = 1 ; i <= n ; i ++) val[i] = mul[i] = 1 ;
  for(register int i = 1 ; i <= n - 1 ; i ++) { uint u , v ; cin >> u >> v ; link(u , v) ; }
  for(register int i = 1 ; i <= q ; i ++) {
    char c ; cin >> c ;
    if(c == '+') { uint u , v , w ; cin >> u >> v >> w ; split(u , v) ; pusha(v , w) ; }
    if(c == '-') { uint u , v , u2 , v2 ; cin >> u >> v >> u2 >> v2 ; cut(u , v) ; link(u2 , v2) ; }
    if(c == '*') { uint u , v , w ; cin >> u >> v >> w ; split(u , v) ; pushm(v , w) ; }
    if(c == '/') { uint u , v ; cin >> u >> v ;  split(u , v) ; cout << sum[v] << '\n' ; }
  }
  return 0 ;
}

[ZJOI2012]网络

$map$存边,因为颜色不超过20种,所以用20个$LCT$不断存边删边

#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define fi first
#define se second
#define pb push_back
inline int read() {
	register int x = 0 , f = 1 ;
	register char c = getchar() ;
	for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
	for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c &amp; 15) ;
	return x * f ;
}
template < typename T > inline bool cmax(T &amp; x , T y) {
	return x < y ? (x = y) , 1 : 0 ;
}
template < typename T > inline bool cmin(T &amp; x , T y) {
	return x > y ? (x = y) , 1 : 0 ;
}
template < typename T > inline bool cabs(T &amp; x) {
	return x > 0 ? 1 : (x = - x) , 0 ;
}
inline int QP(int x , int y , int Mod) {
	int ans = 1 ;
	for( ; y ; y >>= 1 , x = (x * x) % Mod)
		if(y &amp; 1) ans = (ans * x) % Mod ;
	return ans ;
}
int  n , m , c , k ;
const int N = 1e4 + 10 ;
int val[N] ;
class LCT {
	public :
	#define ls(x) ch[x][0]
	#define rs(x) ch[x][1]
	int fa[N] , ch[N][2] , rev[N] , cnt[N] , mx[N] ; int s[N] ; int top ;
	inline bool isroot(int x) { return ls(fa[x]) != x &amp;&amp; rs(fa[x]) != x ; }
	inline void pushup(int x){mx[x]=val[x];
		if(ls(x)) cmax(mx[x],mx[ls(x)]);
		if(rs(x)) cmax(mx[x],mx[rs(x)]);
	}
	inline void pushdown(int x){
		if(x&amp;&amp;rev[x]){
			swap(ls(x),rs(x));
			rev[ls(x)]^=1,rev[rs(x)]^=1;
			rev[x]=0;
		}
	}
	inline void rotate(int x){
		int y=fa[x],z=fa[y],d=rs(y)==x;
		if(!isroot(y)) ch[z][rs(z)==y]=x;
		fa[x]=z;fa[y]=x;fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1];ch[x][d^1]=y;
		pushup(y);
	}
	// inline void pushall(int x){if(!isroot(x))pushall(fa[x]);pushdown(x);}
	inline void splay(int x){
		// pushall(x);
		s[top=1]=x;
		for(int i=x;!isroot(i);i=fa[i])s[++top]=fa[i];
		while(top)pushdown(s[top--]);
		for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
			if(!isroot(y))rotate((rs(y)==x)^(rs(z)==y)?x:y);
				rotate(x);
		}pushup(x);
		return ;
	}
	inline void access(int x){
		for(register int y = 0; x ; x = fa[y=x])
			splay(x),rs(x)=y,pushup(x);
		return ;
	}
	inline void makeroot(int x){ access(x);splay(x);rev[x]^=1;}
	inline void split(int x,int y){makeroot(x);access(y);splay(y);}
	inline void link(int x,int y){++ cnt[x] , ++ cnt[y] , makeroot(x),fa[x]=y;splay(x);}
	inline void cut(int x,int y){--cnt[x],--cnt[y],split(x,y),fa[x]=ls(y)=0,pushup(y);}
	inline int findroot(int x){access(x),splay(x),pushdown(x);while(ls(x))pushdown(x=ls(x));return x;}
	inline int query(int x,int y){split(x,y);return mx[y];}
} ;
LCT lct[15] ;
struct node{
	int u,v;
	inline bool operator <(const node &amp; x) const {
		return u < x.u || (u == x.u &amp;&amp; v < x.v) ;
	}
} ; map < node , int > mp ;
signed main() {
	n = read() , m = read() , c = read() ,k = read();
	for(register int i = 1 ; i <= n ; i ++) val[i] = read() ;
	for(register int i = 1 ; i <= m ; i ++) {
		int u = read() , v = read() , w = read() ;
		node edge1 = {u,v};
		node edge2 = {v,u};
		mp[edge1]=mp[edge2]=w;
		lct[w].link(u,v);
	}
	while(k -- ) {
		int opt = read() ;
		if(opt == 0) {
			int x = read() , w = read() ;
			val[x] = w ;
			for(register int i = 0 ; i < c ; i ++)
				lct[i].splay(x) ;
		}
		if(opt == 1) {
			int u = read(),v=read(),w = read() ;
			node edge1 = {u , v} ;
			node edge2 = {v , u} ;
			if(! mp.count(edge1)) { puts("No such edge.") ; continue ;}
			int x = mp[edge1] ;
			if(x == w) { puts("Success.") ; continue ;}
			if(lct[w].cnt[u]>=2 || lct[w].cnt[v]>=2) {
				puts("Error 1.") ;
				continue ;
			}
			if(lct[w].findroot(u) == lct[w].findroot(v)){
				puts("Error 2.") ;
				continue ;
			}
			puts("Success.");
			lct[x].cut(u , v) ;
			lct[w].link(u , v);
			mp[edge1]=mp[edge2]=w;
		}
		if(opt == 2){
			int w = read() , u = read() , v = read() ;
			if(lct[w].findroot(u) != lct[w].findroot(v)) {
				puts("-1") ;
				continue ;
			}
			printf("%lld\n" , lct[w].query(u,v)) ;
		}
	}
	return 0 ;
}

发表评论

textsms
account_circle
email

P1501,ZJOI-2012(LCT)
P1501 [国家集训队]Tree II 题目描述 一棵 $N$个点的树,每个点的初始权值为 $1$。对于这棵树有 $q$ 个操作,每个操作为以下四种操作之一: + u v c:将&nb…
扫描二维码继续阅读
2020-05-23