首页 > 代码库 > codeforces 165D.Beard Graph 解题报告
codeforces 165D.Beard Graph 解题报告
题意:
给一棵树,树的每条边有一种颜色,黑色或白色,一开始所有边均为黑色,有两个操作:
操作1:将第i条边变成白色或将第i条边变成黑色。
操作2 :询问u,v两点之间仅经过黑色变的最短距离。
树链剖分+树状数组
学习树链剖分:
/* 树链剖分: 划分轻重链,效果是将一颗树变成了若干段连续的区间。 向上记录边权*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;const int MAX = 111111;//子树结点数,所在链链头,同链儿子,结点深度,节点在区间的位置,父节点int siz[MAX], top[MAX], son[MAX], dep[MAX], w[MAX], fa[MAX];//链式前向星记录一颗树struct Edge { int v, ne, id;} edge[MAX << 1];int head[MAX], cnt, num;int vis[MAX], pos[MAX];;//第一次dfs,提取基本信息,划分轻重链void Dfs1 (int u, int v) { fa[v] = u, dep[v] = dep[u] + 1; siz[v] = 1; vis[v] = 1; int tem = 0, p = -1; for (int i = head[v]; i != 0; i = edge[i].ne) { int kid = edge[i].v; if (!vis[kid]) { Dfs1 (v, kid); siz[u] += siz[kid]; if (tem < siz[kid]) tem = siz[kid], p = kid; } } son[v] = p;}//第二次DFS,将重链映射到区间void Dfs2 (int h, int v) { top[v] = h; w[v] = ++num; vis[v] = 1; if (son[v] != -1) Dfs2 (h, son[v]); for (int i = head[v]; i != 0; i = edge[i].ne) { int kid = edge[i].v; if (son[v] != kid && !vis[kid]) Dfs2 (kid, kid); pos[edge[i].id] = w[kid]; //边映射到下结点 }}void addE (int u, int v, int num) { edge[++cnt].v = v, edge[cnt].id = num; edge[cnt].ne = head[u], head[u] = cnt;}int A[MAX]; //pos为边的新编号void add (int x, int k) { for (; x <= num; x += x & -x) A[x] += k;}int getsum (int x) { int s = 0; for (; x > 0; x -= x & -x) s += A[x]; return s;}void modify (int x, int k) { x = pos[x]; int sta = getsum (x) - getsum (x - 1); if (sta == k) return; else add (x, k - sta);}void query (int u, int v) { int s = 0, f1 = top[u], f2 = top[v], len = 0; while (f1 != f2) { if (dep[f1] < dep[f2]) { int y = w[v], x = w[f2]; if (f2 != v) { if (s += getsum (y) - getsum (x) ) break; v = f2; len += y - x; } if (s += getsum (x) - getsum (x - 1) ) break; v = fa[v], f2 = top[v]; len++; } else { int y = w[u], x = w[f1]; if (f1 != u) { if (s += getsum (y) - getsum (x) ) break; u = f1; len += y - x; } if (s += getsum (x) - getsum (x - 1) ) break; u = fa[u], f1 = top[u]; len++; } } int y = w[v], x = w[u]; s += getsum (max (y, x) ) - getsum (min (y, x) ); len += abs (y - x); printf ("%d\n", s == 0 ? len : -1);}int n, u, v, m, t;int main() { scanf ("%d", &n); for (int i = 1; i < n; i++) { scanf ("%d %d", &u, &v); addE (u, v, i), addE (v, u, i); } Dfs1 (0, 1); memset (vis, 0, sizeof vis); Dfs2 (1, 1); scanf ("%d", &m); int k, l, r,tol=0; for (int i = 1; i <= m; i++) { scanf ("%d", &k); if (k != 3) { scanf ("%d", &t); modify (t, k == 1 ? 0 : 1); } if (k == 3) { scanf ("%d %d", &l, &r); query (l, r); } }}
codeforces 165D.Beard Graph 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。