首页 > 其他分享 >P2056 [ZJOI2007] 捉迷藏

P2056 [ZJOI2007] 捉迷藏

时间:2024-09-07 12:02:32浏览次数:12  
标签:dep return Fa 捉迷藏 siz top int P2056 ZJOI2007

题意:

给出一个 \(n\) 个点的树,每个点有黑白两种颜色。初始时每个点都是黑色的。\(q\) 次操作,支持:

  • C x 将第 \(x\) 个点的颜色反转。
  • G 询问树上两个黑色点的最远距离。

分析:

尝试使用点分树,对于一条路径,可以从点分树的 \(lca\) 处统计,由于涉及到删除和添加两种操作,因此可以用 multiset 来维护。

记 \(C_{i}\) 表示 \(i\) 的点分树子树内所有黑点到 \(i\) 的点分树父亲距离的可重集。因为需要保证每次的 \(C_{i}\) 都是不同子树,记 \(B_{i}\) 表示 \(i\) 的点分树儿子的 \(C_{j}\) 的可重集(特别的,如果 \(i\) 是黑色点,要把 \(0\) 也放进 \(B_{i}\) 里)。\(A\) 表示所有 \(B_{i}\) 的最大值和次大值之和的可重集(当然也有其他维护方法)。

由于 multiset 常数太大,使用双堆来模拟。具体地,加入一个数时放在堆 \(x\) 里,删除一个数时放在堆 \(y\) 里,查询最大值时,比较两个堆的堆顶,如果相同就同时弹出,直到堆顶不同为止,此时堆 \(x\) 的堆顶就是最大值。删除最大值同理。时间复杂度同样为 \(O(n + m \log^2 n)\)。只不过堆比 multiset 快了 \(1\) 倍。

代码:

#include<bits/stdc++.h>
#define N 100005 
using namespace std;

int n, m, Q;
vector<int>p[N];

int top[N], fa[N], dep[N], siz[N], son[N];
void dfs1(int x, int father) {
	fa[x] = father;
	dep[x] = dep[father] + 1;
	siz[x] = 1;
	int Maxson = -1;
	for(auto y : p[x]) {
		if(y == father) continue;
		dfs1(y, x);
		siz[x] += siz[y];
		if(siz[y] > Maxson) {
			Maxson = siz[y];
			son[x] = y;
		}
	}
}
void dfs2(int x, int topf) {
	top[x] = topf;
	if(son[x]) dfs2(son[x], topf);
	for(auto y : p[x]) {
		if(top[y]) continue;
		dfs2(y, y);
	}
}
int lca(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
    return dep[x] < dep[y] ? x : y;
}
int dis(int x, int y) {
	return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

int Fa[N], vis[N], root, Num, sum;
void Getroot(int x, int fa) {
	siz[x] = 1;
	int Maxsiz = 0;
	for(auto y : p[x]) {
		if(y == fa || vis[y]) continue; 
		Getroot(y, x);
		siz[x] += siz[y];
		Maxsiz = max(Maxsiz, siz[y]);
	}
	Maxsiz = max(Maxsiz, sum - siz[x]);
	if(Maxsiz < Num) {
		Num = Maxsiz;
		root = x;
	}
}
void Build(int x) {
	vis[x] = 1;
	for(auto y : p[x]) {
		if(vis[y]) continue;
		Getroot(y, 0); //注意要先算出子连通块大小, 再去找重心 
		Num = 1e9, sum = siz[y];
		Getroot(y, 0);
		Fa[root] = x;
		Build(root);
	}
}

int ljm[N], tot;

struct Set { //双堆模拟set 
	priority_queue<int>x, y;
	void Add(int a) { //加入a 
		x.push(a);
	}
	void Del(int a) { //删除a 
		y.push(a);
	}
	int Top() { //求最大值 
		while(y.size() && x.top() == y.top()) x.pop(), y.pop();
		return x.top();
	}
	void Pop() { //删除最大值 
		while(y.size() && x.top() == y.top()) x.pop(), y.pop();
		x.pop();
	}
	int Size() { //求集合大小 
		return x.size() - y.size();
	}
	int SecTop() { //求次大值 
		int A = Top(); Pop();
		int B = Top(); Add(A);
		return B;
	}
}C[N], B[N], A; //C[u]表示u子树内所有点距离Fa[u]的集合, B[u]表示u的儿子的C[u]的最大值的集合, A 表示 B[u]最大值和次大值 ;


int Get_B(int x) {
	return B[x].Top() + B[x].SecTop();
}

int Get_C(int x) {
    return C[x].Top();
}

void upd(int x) {
	int i = x;

	if(B[i].Size() >= 2) A.Del(Get_B(i)); //删原来A
	if(ljm[i] == 0) B[i].Add(0);
	else B[i].Del(0);
	if(B[i].Size() >= 2) A.Add(Get_B(i)); //加现在A

	while(Fa[x]) {
		if(B[Fa[x]].Size() >= 2) A.Del(Get_B(Fa[x])); //删原来A

		if(C[x].Size()) B[Fa[x]].Del(Get_C(x)); //删原来B

		if(ljm[i] == 0) C[x].Add(dis(i, Fa[x])); 
		else C[x].Del(dis(i, Fa[x])); //更新C

		if(C[x].Size()) B[Fa[x]].Add(Get_C(x)); //加现在B
		
		if(B[Fa[x]].Size() >= 2) A.Add(Get_B(Fa[x])); //加现在A
		x = Fa[x];
	}
	if(ljm[i] == 0) tot++;
	else tot--;
	ljm[i] ^= 1;
}

int query() {
	if(tot == 0) return -1;
	else if(tot == 1) return 0;
	else return A.Top();
}

void work() {
    for(int i = 1; i <= n; i++) upd(i);
    cin >> Q;
    while(Q--) {
        char opt;
        cin >> opt;
        if(opt == 'C') {
            int x;
            cin >> x;
            upd(x);
        }
        else cout << query() << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		p[u].push_back(v);
		p[v].push_back(u); 
	}
	dfs1(1, 0);
	dfs2(1, 1);
	Num = 1e9, sum = n; 
	Getroot(1, 0);
	Build(root);
    work();
	return 0;
	
}

标签:dep,return,Fa,捉迷藏,siz,top,int,P2056,ZJOI2007
From: https://www.cnblogs.com/xcs123/p/18401515

相关文章

  • [lnsyoj539/luoguP2120/ZJOI2007]仓库建设
    题意懒了(sol显然DP设计状态:\(f_i\)表示\(1\simi\)的工厂中,在第\(i\)个工厂处建设仓库的最小代价;状态转移:由题意,显然可得:\[f_i=\min_{j=1}^{i-1}\{f_j+c_i+\sum_{k=j+1}^i(x_i-x_k)\cdotp_k\}\]我们发现中间的一坨求和可以通过前缀和的方式预处理出\(sum_i=......
  • P2120 [ZJOI2007] 仓库建设
    题目大意\(n\)个工厂,每个工厂有\(p_i\)的货物,货物运输一个单位距离的费用是\(1\),工厂可以建造仓库,费用为\(c_i\)。工厂与工厂\(1\)的距离为\(x_i\)。要求将货物运送到下一个最近的仓库,求最小费用。\(1\leqn\leq10^6\)思路先考虑最基本的动规:设\(f_i\)表示在这里......
  • Luogu P1110 [ZJOI2007] 报表统计
    题目描述给定一个长度为\(n\)的整数序列\(a\),有以下三种操作:INSERTix:\(i\)位置后面添加一个新元素\(x\),下一个元素挂在这个元素后面。MIN_GAP:查询相邻元素差值的最小值。MIN_SORT_GAP:查询元素中最接近的两个元素的差值。题目解析平衡树经典题目。建立\(2\)棵平衡......
  • C138 线段树分治 P2056 [ZJOI2007] 捉迷藏
    视频链接:C138线段树分治P2056[ZJOI2007]捉迷藏_哔哩哔哩_bilibili   P2056[ZJOI2007]捉迷藏-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(nlognlogn)#include<iostream>#include<cstring>#include<algorithm>#include<vector>#inclu......
  • NOI模拟 捉迷藏
    涉及知识点:博弈论题意在一个树上,A和B可以通过边在节点间移动,每回合可以不移动,或者移动到有边直接连接的节点。A在抓B,当A与B处于同一个节点时即为被抓住,可以发现无论如何B最后都会被抓住,你需要添加最小数量的边使得B有策略可以永远不会被抓住。思路最终的必败态是......
  • P1110 [ZJOI2007] 报表统计 题解
    考察点:STL的熟练运用。记:\(l_i\)表示序列中不超过\(a_i\)的最大数,\(r_i\)表示序列中超过\(a_i\)的最小数。开一个vectorinsert[N]存储\(a_i\)后面插入的所有数字。首先,我们使用一个multisets1来存储相邻元素的差的绝对值,然后再开一个multisets2来存储当前出......
  • 捉迷藏
    这里主要是对蓝书上做法的补充首先看到这道题目,我们假设已经知道要选哪些点了,那我们在原图\(G\)上每选一个点,与这个点有关的路径上的所有点都要被打上标记,打上标记的点就不能再选了,所以我们选的点就是每次都没有标记的点像这种“与一点有关的所有路径的所有点”,可以通过传递闭包......
  • P1129 [ZJOI2007] 矩阵游戏 建模部分
    link题解没一个说为什么能用最小割的...(当然可能是只有我不知道)设交换后行、列数相同的第\(x\)行和第\(y\)列(\(x,y\)为原始位置),发现它们的交点现在位于\((i,i)\),原来位于\((x,y)\)。因为无论怎么交换位置,原来的交点仍是交点。所以可以得出一个构造方案:先选定\(n\)个点......
  • 斜率优化 [ZJOI2007] 仓库建设
    [ZJOI2007]仓库建设题目描述L公司有\(n\)个工厂,由高到低分布在一座山上,工厂\(1\)在山顶,工厂\(n\)在山脚。由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于......
  • P1129 [ZJOI2007] 矩阵游戏
    挺喜欢的一题。首先我们很容易观察到一个性质:每一行和每一列上的黑色方格的数量是不变的,只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格,直接输出No即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。这时有一个结论:若有......