HDU5039--Hilarity DFS序+线段树区间更新 14年北京网络赛

题意：n个点的树，每个条边权值为0或者1， q次操作

Q 路径边权抑或和为1的点对数，（u， v）（v, u）算2个。

M i修改第i条边的权值如果是0则变成1，否则变成0

作法：我们可以求出每个点到根节点路径边权抑或和为val，那么ans = val等于0的个数乘val等于1的个数再乘2。

注意到每一次修改操作，只会影响以u为根的子树（假设边为u----v dep[v] > dep[u]），那么每次只需把子树区间的值与1抑或就行了。这一步可以用线段树区间更新。

比赛时过的人好少。。。好奇怪。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int MAXN = 3e4 + 1;
  4 struct Edge {
  5     int to, cost;
  6     Edge (int to, int cost){
  7         this->to = to, this->cost = cost;
  8     }
  9 };
 10 vector <Edge> G[MAXN];
 11 int val[MAXN];
 12 int siz[MAXN], pt1[MAXN], pt2[MAXN], IDX, dep[MAXN];
 13 void dfs(int u, int father, int k) {
 14     val[u] = k;
 15     dep[u] = dep[father] + 1;
 16     pt1[u] = ++IDX;
 17     for (Edge e: G[u]) {
 18         int v = e.to;
 19         if (v != father) {
 20             dfs(v, u, k^e.cost);
 21         }
 22     }
 23     pt2[u] = IDX;
 24 }
 25 int seg[2][MAXN << 2], lazy[MAXN << 2];
 26 void push_down (int pos) {
 27     if (lazy[pos]) {
 28         swap(seg[0][pos<<1], seg[1][pos<<1]);
 29         swap(seg[0][pos<<1|1], seg[1][pos<<1|1]);
 30         lazy[pos<<1] ^= lazy[pos];
 31         lazy[pos<<1|1] ^= lazy[pos];
 32         lazy[pos] = 0;
 33     }
 34 }
 35 void build (int l, int r, int pos, int x, int d) {
 36     if (l == r) {
 37         seg[0][pos] = d == 0;
 38         seg[1][pos] = d == 1;
 39         return;
 40     }
 41     int mid = (l + r) >> 1;
 42     if (x <= mid) {
 43         build(l, mid, pos<<1, x, d);
 44     } else {
 45         build(mid+1, r, pos<<1|1, x, d);
 46     }
 47     seg[0][pos] = seg[0][pos<<1] + seg[0][pos<<1|1];
 48     seg[1][pos] = seg[1][pos<<1] + seg[1][pos<<1|1];
 49 }
 50 void update (int l, int r, int pos, int ua, int ub) {
 51     if (ua <= l && ub >= r) {
 52         lazy[pos] ^= 1;
 53         swap(seg[0][pos], seg[1][pos]);
 54         return;
 55     }
 56     push_down(pos);
 57     int mid = (l + r) >> 1;
 58     if (ua <= mid) {
 59         update(l, mid, pos<<1, ua, ub);
 60     }
 61     if (ub > mid) {
 62         update(mid+1, r, pos<<1|1, ua, ub);
 63     }
 64     seg[0][pos] = seg[0][pos<<1] + seg[0][pos<<1|1];
 65     seg[1][pos] = seg[1][pos<<1] + seg[1][pos<<1|1];
 66 }
 67 void init () {
 68     IDX = 0;
 69     memset(lazy, 0, sizeof (lazy));
 70     memset(seg, 0, sizeof seg);
 71     for (int i = 0; i < MAXN; i++) {
 72         G[i].clear();
 73     }
 74 }
 75 pair <int, int> edge[MAXN];
 76 int main() {
 77 #ifndef ONLINE_JUDGE
 78     freopen("in.txt", "r", stdin);
 79 #endif // ONLINE_JUDGE
 80     int T, cas = 1;
 81     scanf ("%d", &T);
 82     while (T--) {
 83         init();
 84         int n, q;
 85         int tot = 0;
 86         map <string, int> mp;
 87         scanf ("%d", &n);
 88         for (int i = 1; i <= n; i++) {
 89             char buff[15];
 90             scanf ("%s", buff);
 91             mp[buff] = ++tot;
 92         }
 93         for (int i = 0; i < n-1; i++) {
 94             char name1[15], name2[15];
 95             int status;
 96             scanf ("%s%s%d", name1, name2, &status);
 97             edge[i] = make_pair(mp[name1], mp[name2]);
 98             G[edge[i].first].push_back(Edge(edge[i].second, status));
 99             G[edge[i].second].push_back(Edge(edge[i].first, status));
100         }
101         dfs(1, 0, 0);
102         build(1, IDX, 1, pt1[1], 0);
103         for (int i = 0; i < n-1; i++) {
104             int u = edge[i].first;
105             int v = edge[i].second;
106             if (dep[u] > dep[v]) {
107                 swap(u, v);
108             }
109             build(1, IDX, 1, pt1[v], val[v]);
110         }
111         scanf ("%d", &q);
112         printf("Case #%d:
", cas++);
113         for (int i = 0; i < q; i++) {
114             char kind[5];
115             scanf ("%s", kind);
116             if (kind[0] == 'Q') {
117                 printf("%d
", seg[0][1] * seg[1][1] * 2);
118             } else {
119                 int e;
120                 scanf ("%d", &e);
121                 int u = edge[e-1].first;
122                 int v = edge[e-1].second;
123                 if (dep[u] > dep[v]) {
124                     swap(u, v);
125                 }
126                 update(1, IDX, 1, pt1[v], pt2[v]);
127             }
128         }
129     }
130     return 0;
131 }