首页 > 编程语言 >2023年国际大学生程序设计竞赛(ACM-ICPC)新疆赛区 A.The Number Of Black Edges

2023年国际大学生程序设计竞赛(ACM-ICPC)新疆赛区 A.The Number Of Black Edges

时间:2023-05-27 11:56:57浏览次数:54  
标签:黑色 奇数 int modify Number ACM ICPC 节点 id

传送门

大致题意:

  爱丽丝得到一棵树,树上有n个节点,索引从1到n。树上的每条边可以是黑色或白色,所有的边最初都是白色的。有三种操作: 1. 将一条边的颜色改为黑色。2. 将一条边的颜色改为白色。3. 3.给定一个节点索引,计算从所有奇数节点到该节点的简单路径上的黑色边的数量之和。请注意,简单路径是指两个节点之间的路径,该路径对任何节点的访问都不超过一次。读入一个n和一个m,紧接着读入n-1行,每行两个节点u,v表示u和v有连边,第几行就表示是第几个边。读入m个询问,询问如提议所示。

解题思路:

  发现如果有一条边从白色变成了黑色,我们可以认为黑的边把这个树分成了左右两个部分,右边的任意一个点到右边的任意一个点的简单路径都不会经过这个黑色的边,也就是说左边的点无法对左边的点造成任何贡献,右边的点无法对右边的点造成任何贡献。但是左边的点和右边的点可能会有贡献。如果我们知道左边的奇数的点的数量是x1,右边的奇数点的数量为x2,那么右边所有点被奇数点的拜访且经过黑色边的次数就会增加x1的数量,左边所有点被奇数点拜访的数量且经过黑色边的次数都会加x2。所以考虑用线段树维护每个点答案即可。树上跑dfs序建线段树,统计出每个点的子树大小和深度和子树有多少奇数结点。对于第x条边我们可以知道第x个边对应的两个点是谁,我们已经预处理求出深度最大的那个点中有多少奇数点数量sum,那么深度小的那个点对应的奇数结点数量就是(n + 1) / 2 - sum,sum就是我们说的x1, (n + 1) / 2 - sum 就是说的x2。需要注意的地方就是需要开一个数组记录当前边的颜色,如果把一个白色边染成白色或者把一个黑色边染成黑色是不会对答案造成任何影响的。

#include <bits/stdc++.h>

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using ll = long long;

typedef std::pair<int, int> PII;

int a[N];
int n, m;

int h[N], ne[N << 1], e[N << 1], idx;
int sz[N], fa[N], id[N], rid[N], timedelta, dep[N], odd[N];
bool color[N];

inline void add(int a, int b) {
	ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

inline void dfs(int u, int father, int depth) {
	id[u] = ++ timedelta, rid[timedelta] = u;
	sz[u] = 1; dep[u] = depth; 
	if (u & 1) odd[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == father) continue;
		dfs(j, u, depth + 1);
		sz[u] += sz[j];
		odd[u] += odd[j];
	}
}

struct node {
	ll ans, tag;
}tr[N << 2];

#define ls u << 1
#define rs u << 1 | 1

inline void pushdown(int u) {
	if (tr[u].tag) {
		tr[ls].tag += tr[u].tag;
		tr[rs].tag += tr[u].tag;
		tr[ls].ans += tr[u].tag;
		tr[rs].ans += tr[u].tag;
		tr[u].tag = 0;
	}
}

inline void modify(int u, int L, int R, int l, int r, int v, int how) {
	if (L >= l && R <= r) {
		if (how) {
			if (L == R) tr[u].ans += v;
			else tr[u].tag += v;
		} else {
			if (L == R) tr[u].ans -= v;
			else tr[u].tag -= v;
		}
		return ;
	}
	
	pushdown(u);
	
	int mid = L + R >> 1;
	if (l <= mid) modify(ls, L, mid, l, r, v, how);
	if (r > mid) modify(rs, mid + 1, R, l, r, v, how);
}

inline ll query(int u, int L, int R, int x) {
	if (L == R) return tr[u].ans;
	
	pushdown(u);
	
	int mid = L + R >> 1;
	if (x <= mid) return query(ls, L, mid, x);
	return query(rs, mid + 1, R, x);
}

inline void solve() {
	memset(h, -1, sizeof h);
	
	std::cin >> n >> m;
	
	std::vector<PII> edge; 
	for (int i = 2; i <= n; i ++) {
		int a, b;
		std::cin >> a >> b;
		add(a, b);
		add(b, a);
		edge.push_back({a, b});
	}
	
	int tot = n + 1 >> 1; // 编号为奇数的点的个数
	
	dfs(1, -1, 1);
	
	while (m --) {
		int op, x;
		std::cin >> op >> x;
		if (op == 2) { // 染成黑色
		    x --;
			if (!color[x]) continue;
			color[x] = false;
			auto [u, v] = edge[x];
		
			if (dep[u] < dep[v]) std::swap(u, v);
			int top = tot - odd[u];
			modify(1, 1, n, id[u], id[u] + sz[u] - 1, top, 0);
			if (id[u] > 1)
			modify(1, 1, n, 1, id[u] - 1, odd[u], 0);
			if (id[u] + sz[u] <= n)
			modify(1, 1, n, id[u] + sz[u], n, odd[u], 0); 
		} else if (op == 1) { // 染成白色
		    x --;
			if (color[x]) continue;
			color[x] = true;
			auto [u, v] = edge[x];
			if (dep[u] < dep[v]) std::swap(u, v);
			int top = tot - odd[u];
			modify(1, 1, n, id[u], id[u] + sz[u] - 1, top, 1);
			if (id[u] > 1) 
			modify(1, 1, n, 1, id[u] - 1, odd[u], 1);
			if (id[u] + sz[u] - 1 < n)
			modify(1, 1, n, id[u] + sz[u], n, odd[u], 1); 
		} else { // 求答案
			std::cout << query(1, 1, n, id[x]) << '\n';
		}
		
	}
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int _ = 1;
    //std::cin >> _;
    while (_ --) solve();
    
    return 0;
}

标签:黑色,奇数,int,modify,Number,ACM,ICPC,节点,id
From: https://www.cnblogs.com/qdhys/p/17436510.html

相关文章

  • 1342. Number of Steps to Reduce a Number to Zero刷题笔记
    easy题,按照逻辑写就行了classSolution:defnumberOfSteps(self,num:int)->int:step=0whilenum:ifnum%2==0:num=num/2else:num-=1step+=1returnste......
  • 河北工业大学 ACM 集训队 2023 年夏季选拔 题解 12/12
    https://ac.nowcoder.com/acm/contest/59007A假设数字n有len位则小len的长度,每个都有九个方案。长度和len一样的,至少有n[0]-1种方案n[0]n[0]n[0]...的这个方案暴力地跑一遍看看是不是小于等于n即可#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;in......
  • 2023年icpc江西省赛-D
    题目链接:https://codeforces.com/gym/104385/problem/D我的三维空间dp思路:设dp[i][j][k][0/1]表示前i个操作已经弹出了j个值,并且当前有k个连续弹出的数,当前序列合不合法的方案数,这样的dp优化成二维空间的,所以舍弃。正解思路:最朴素的想法是三维暴力dp,设dp[i][j][0/1]表示前i个pus......
  • el-input的maxlength属性在number类型时需要特殊处理
    maxlength在开发中,输入框一定要限制长度,之前在开发中都没注意过输入字符串的时候直接使用maxlength就可以了但是type是number的时候,maxlength就不起作用了.number默认情况下,不管用户输入字符串还是数字,在获取的值都是字符串.number可以将字符串转换成数字但是我自己测试......
  • 2021 ICPC 江西省大学生程序设计竞赛(正式赛)
    链接:https://ac.nowcoder.com/acm/contest/21592BC++Code#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;voidsolve(){intx,y;cin>>x>>y;intcnt=0;vector<int>ans;while(1)......
  • 河南省第十四届icpc大学生程序设计竞赛-clk
    这次比赛赛程比较长,520出发,521,回学校,出发的那一天有点热,感觉不是很好,而且那一天感觉有点生病,应该只是普通感冒,热身赛的时候被oier吊打,省实验真厉害,晚上回酒店后,我喊队友,补了前年的icpc的省赛题,很友好,轻松就A了五道题,用时也不是特别多,还做了情人节的520pta,做的有点慢,导致有一道题没......
  • 2023 (ICPC) Jiangxi Provincial Contest -- Official Contest
    2023(ICPC)JiangxiProvincialContest--OfficialContest A-DrillWoodtoMakeFire思路:n>=s*vB-WonderfulArray思路:对a进行a%m,不会对结果造成影响,则0<=bi+1-bi<m。可以求bi+1%m<bi%m的个数,等价于bi+1/m>bi/m,整体来看,就是求bn/m#include<bits/stdc++.h>using......
  • acme.sh数据迁移
    acme.sh数据迁移1.1.安装脚本在新服务器安装acme.sh脚本工具curlhttps://get.acme.sh|sh#orwget-O-https://get.acme.sh|shll~/.acme.sh/aliasacme.sh=~/.acme.sh/acme.shll~/.acme.sh/1.2.打包备份acme.sh数据cd/root/ll-atar-zcvfacme.sh......
  • 2023(ICPC)江西省赛I题题解
    I.Tree题意:两种操作,操作1:将一棵树一条路径上的边权异或上一个数,操作2:或者询问一个点周围所有边权的异或和。题解:首先,异或有一个性质A⨁A=0⇒A⨁B⨁A=B在进行操作一时,对X到Y的简单路径上的每一条边权异或,会是这样的情况X_w1_Z_w2_P_w3_Y,根据上面......
  • 2023ICPC江西省赛补题(B,C)
    题目:B(规律)题意:给你长度为k的a序列,然后根据题目要求构造长度为n的b序列,求b序列中有多少个\(b_i\)%m\(<=b_{i+1}\)%m(0<=i<n)。思路:因为数据范围过大,很明显这题不能暴力求解。首先很明显我们可以将a序列全部%m,这显然不会对答案造成影响,然后我们枚举样例就会......