SPOJ COT2 Count on a tree II（树上莫队）

题目链接：http://www.spoj.com/problems/COT2/

You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.

We will ask you to perfrom the following operation:

u v : ask for how many different integers that represent the weight of nodes there are on the path from u to v.

Input

In the first line there are two integers N and M.(N<=40000,M<=100000)

In the second line there are N integers.The ith integer denotes the weight of the ith node.

In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).

In the next M lines,each line contains two integers u v,which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.

Output

For each operation,print its result.

题目大意：给一棵树，每个点有一个权值。多次询问路径(a, b)上有多少个权值不同的点。

思路：参考VFK WC 2013 糖果公园 park 题解（此题比COT2要难。）

http://vfleaking.blog.163.com/blog/static/174807634201311011201627/

代码（2.37S）：

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXV = ;

 const int MAXE = MAXV << ;

 const int MAXQ = ;

 const int MLOG = ;

 namespace Bilibili {

 int head[MAXV], val[MAXV], ecnt;

 int to[MAXE], next[MAXE];

 int n, m;

 int stk[MAXV], top;

 int block[MAXV], bcnt, bsize;

 struct Query {

     int u, v, id;

     void read(int i) {

         id = i;

         scanf("%d%d", &u, &v);

     }

     void adjust() {

         if(block[u] > block[v]) swap(u, v);

     }

     bool operator < (const Query &rhs) const {

         if(block[u] != block[rhs.u]) return block[u] < block[rhs.u];

         return block[v] < block[rhs.v];

     }

 } ask[MAXQ];

 int ans[MAXQ];

 /// Graph

 void init() {

     memset(head + , -, n * sizeof(int));

     ecnt = ;

 }

 void add_edge(int u, int v) {

     to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;

     to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++;

 }

 void gethash(int a[], int n) {

     static int tmp[MAXV];

     int cnt = ;

     for(int i = ; i <= n; ++i) tmp[cnt++] = a[i];

     sort(tmp, tmp + cnt);

     cnt = unique(tmp, tmp + cnt) - tmp;

     for(int i = ; i <= n; ++i)

         a[i] = lower_bound(tmp, tmp + cnt, a[i]) - tmp + ;

 }

 void read() {

     scanf("%d%d", &n, &m);

     for(int i = ; i <= n; ++i) scanf("%d", &val[i]);

     gethash(val, n);

     init();

     for(int i = , u, v; i < n; ++i) {

         scanf("%d%d", &u, &v);

         add_edge(u, v);

     }

     for(int i = ; i < m; ++i) ask[i].read(i);

 }

 /// find_block

 void add_block(int &cnt) {

     while(cnt--) block[stk[--top]] = bcnt;

     bcnt++;

     cnt = ;

 }

 void rest_block() {

     while(top) block[stk[--top]] = bcnt - ;

 }

 int dfs_block(int u, int f) {

     int size = ;

     for(int p = head[u]; ~p; p = next[p]) {

         int v = to[p];

         if(v == f) continue;

         size += dfs_block(v, u);

         if(size >= bsize) add_block(size);

     }

     stk[top++] = u;

     size++;

     if(size >= bsize) add_block(size);

     return size;

 }

 void init_block() {

     bsize = max(, (int)sqrt(n));

     dfs_block(, );

     rest_block();

 }

 /// ask_rmq

 int fa[MLOG][MAXV];

 int dep[MAXV];

 void dfs_lca(int u, int f, int depth) {

     dep[u] = depth;

     fa[][u] = f;

     for(int p = head[u]; ~p; p = next[p]) {

         int v = to[p];

         if(v != f) dfs_lca(v, u, depth + );

     }

 }

 void init_lca() {

     dfs_lca(, -, );

     for(int k = ; k +  < MLOG; ++k) {

         for(int u = ; u <= n; ++u) {

             if(fa[k][u] == -) fa[k + ][u] = -;

             else fa[k + ][u] = fa[k][fa[k][u]];

         }

     }

 }

 int ask_lca(int u, int v) {

     if(dep[u] < dep[v]) swap(u, v);

     for(int k = ; k < MLOG; ++k) {

         if((dep[u] - dep[v]) & ( << k)) u = fa[k][u];

     }

     if(u == v) return u;

     for(int k = MLOG - ; k >= ; --k) {

         if(fa[k][u] != fa[k][v])

             u = fa[k][u], v = fa[k][v];

     }

     return fa[][u];

 }

 /// modui

 bool vis[MAXV];

 int diff, cnt[MAXV];

 void xorNode(int u) {

     if(vis[u]) vis[u] = false, diff -= (--cnt[val[u]] == );

     else vis[u] = true, diff += (++cnt[val[u]] == );

 }

 void xorPathWithoutLca(int u, int v) {

     if(dep[u] < dep[v]) swap(u, v);

     while(dep[u] != dep[v])

         xorNode(u), u = fa[][u];

     while(u != v)

         xorNode(u), u = fa[][u],

         xorNode(v), v = fa[][v];

 }

 void moveNode(int u, int v, int taru, int tarv) {

     xorPathWithoutLca(u, taru);

     xorPathWithoutLca(v, tarv);

     //printf("debug %d %d\n", ask_lca(u, v), ask_lca(taru, tarv));

     xorNode(ask_lca(u, v));

     xorNode(ask_lca(taru, tarv));

 }

 void make_ans() {

     for(int i = ; i < m; ++i) ask[i].adjust();

     sort(ask, ask + m);

     int nowu = , nowv = ; xorNode();

     for(int i = ; i < m; ++i) {

         moveNode(nowu, nowv, ask[i].u, ask[i].v);

         ans[ask[i].id] = diff;

         nowu = ask[i].u, nowv = ask[i].v;

     }

 }

 void print_ans() {

     for(int i = ; i < m; ++i)

         printf("%d\n", ans[i]);

 }

 void solve() {

     read();

     init_block();

     init_lca();

     make_ans();

     print_ans();

 }

 };

 int main() {

     Bilibili::solve();

 }

巴特西

SPOJ COT2 Count on a tree II（树上莫队）

Input

Output

最新文章

热门文章