BZOJ3757 苹果树

浏览数：27 / 时间：2015年06月11日

树上的莫队算法。。。话说糖果公园也是的说？、、、蒟蒻不会233

先搞出dfs序，然后对dfs序直接莫队就好了。。。

但是写的我蛋疼啊。。。3h就一道题还让不让人活？

  1 /**************************************************************
  2     Problem: 3757
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:4000 ms
  7     Memory:23096 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cmath>
 13 #include <algorithm>
 14  
 15 using namespace std;
 16 const int N = 100005;
 17 const int Maxlen = 3500005;
 18  
 19 int n, Q;
 20 int tot, first[N];
 21 int dfn, c[N], w[N << 1];
 22 int sz, pos[N << 1];
 23 int l, r, Lca;
 24 int sum, cnt[N], ans[N];
 25 bool vis[N << 1];
 26 char buf[Maxlen], *C = buf;
 27 int Len;
 28  
 29 struct tree_node {
 30     int dep, fa[20];
 31     bool vis;
 32     int st, en;
 33 } tr[N];
 34  
 35 struct edges {
 36     int next, to;
 37     edges() {}
 38     edges(int _n, int _t) : next(_n), to(_t) {}
 39 } e[N << 1];
 40  
 41 struct query {
 42     int l, r, lca, a, b, id;
 43      
 44     inline bool operator < (const query &b) const {
 45         return pos[l] == pos[b.l] ? r < b.r : pos[l] < pos[b.l];
 46     }
 47 }a[N];
 48  
 49 void Add_Edges(int x, int y) {
 50     e[++tot] = edges(first[x], y), first[x] = tot;
 51     e[++tot] = edges(first[y], x), first[y] = tot;
 52 }
 53  
 54 inline int read() {
 55     int x = 0;
 56     while (*C < ‘0‘ || ‘9‘ < *C) ++C;
 57     while (‘0‘ <= *C && *C <= ‘9‘)
 58         x = x * 10 + *C - ‘0‘, ++C;
 59     return x;
 60 }
 61  
 62 void dfs(int p) {
 63     int x, y;
 64     w[tr[p].st = ++dfn] = p, tr[p].vis = 1;
 65     for (x = 1; x <= 17; ++x)
 66         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1];
 67     for (x = first[p]; x; x = e[x].next)
 68         if (!tr[y = e[x].to].vis)
 69             tr[y].dep = tr[p].dep + 1, tr[y].fa[0] = p, dfs(y);
 70     w[tr[p].en = ++dfn] = p;
 71 }
 72  
 73 inline int lca(int x, int y) {
 74     int i;
 75     if (x == y) return x;
 76     if (tr[x].dep < tr[y].dep) swap(x, y);
 77     for (i = 17; i >= 0; --i)
 78         if (tr[tr[x].fa[i]].dep >= tr[y].dep) x = tr[x].fa[i];
 79     if (x == y) return x;
 80     for (i = 17; i >= 0; --i)
 81         if (tr[x].fa[i] != tr[y].fa[i]) x = tr[x].fa[i], y = tr[y].fa[i];
 82     return tr[x].fa[0];
 83 }
 84  
 85 inline int check(int x, int y) {
 86     return x != y && cnt[x] && cnt[y];
 87 }
 88  
 89 inline void update(int x) {
 90     if (vis[x]) {
 91         if (!(--cnt[c[x]])) --sum;
 92     } else
 93         if (!(cnt[c[x]]++)) ++sum;
 94     vis[x] ^= 1;
 95 }
 96  
 97 int main() {
 98     Len = fread(C, 1, Maxlen, stdin);
 99     buf[Len] = ‘\0‘;
100     int i, x, y;
101     n = read(), Q = read();
102     for (i = 1; i <= n; ++i)
103         c[i] = read();
104     for (i = 1; i <= n; ++i) {
105         x = read(), y = read();
106         if (x && y) Add_Edges(x, y);
107     }
108     tr[1].dep = 1;
109     dfs(1);
110      
111     sz = (int) sqrt(n * 2 + 0.5);
112     for (i = 1; i <= dfn; ++i)
113         pos[i] = (i - 1) / sz + 1;
114     for (i = 1; i <= Q; ++i) {
115         x = read(), y = read();
116         a[i].a = read(), a[i].b = read(), a[i].id = i;
117         if (tr[x].st > tr[y].st) swap(x, y);
118         Lca = lca(x, y);
119         if (Lca == x)
120             a[i].l = tr[x].st, a[i].r = tr[y].st;
121         else a[i].l = tr[x].en, a[i].r = tr[y].st, a[i].lca = Lca;
122     }
123      
124     sort(a + 1, a + Q + 1);
125     for (i = 1, l = 1, r = 0; i <= Q; ++i) {
126         while (r < a[i].r) update(w[++r]);
127         while (r > a[i].r) update(w[r--]);
128         while (l < a[i].l) update(w[l++]);
129         while (l > a[i].l) update(w[--l]);
130         if (a[i].lca) update(a[i].lca);
131         ans[a[i].id] = sum - check(a[i].a, a[i].b);
132         if (a[i].lca) update(a[i].lca);
133     }
134     for (i = 1; i <= Q; ++i)
135         printf("%d\n", ans[i]);
136     return 0;
137 }