首页 > 代码库 > 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);        }    }}
View Code

 

codeforces 165D.Beard Graph 解题报告