SPOJ10707 COT2-Count on a tree II

COT2 - Count on a tree II

中文题意

离线询问一颗树上路径(u,v)中经过所有点的权值的种类数。

题解

树上莫队。即在树的欧拉序列上进行莫队。同一个点加第一次时增加，第二次时减去增加的影响。

错误记录

用了tarjan LCA，并偷懒将询问和莫队都用一个node表示。意味着每一个询问都要开两个node，写莫队排序sort的时候注意结构体数组长度！莫队排序后两个相同的node不一定相邻，因为可能出现node[i].l/size和node[j].l/size相等，但是node[i].l和node[j].l并不相等的情况。卡了半天。
题目信息不全，权值据说是1e9，别忘了离散化

#include 
#include 
#include 
#include 
#include 
#include void swap(int &a, int &b){int tmp = a;a = b, b = tmp;}
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a < b ? a : b;}
void read(int &x)
{x = 0;char ch = getchar(), c = ch;while(ch < '0' || ch > '9') c = ch, ch = getchar();while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();if(c == '-') x = -x;
}const int INF = 0x3f3f3f3f;
const int MAXN = 1000000;
const int MAXM = 1000000;struct Edge
{int u, v, nxt;Edge(int _u, int _v, int _nxt){u = _u, v = _v, nxt = _nxt;}Edge(){}
}edge[MAXN << 1];
int head[MAXN], cnt;
void insert(int a, int b)
{edge[++ cnt] = Edge(a, b, head[a]), head[a] = cnt;edge[++ cnt] = Edge(b, a, head[b]), head[b] = cnt;
}int tong[MAXN], val[MAXN], num[MAXN], id[MAXN];
int fa[MAXN], seq[MAXN], st[MAXN], et[MAXN], t, sum; 
int n, m;void dfs(int x)
{seq[++ t] = x;st[x] = t;for(int pos = head[x];pos;pos = edge[pos].nxt){int v = edge[pos].v;if(v == fa[x]) continue;fa[v] = x;dfs(v);}seq[++ t] = x;et[x] = t;
}int cmp(int a, int b)
{return val[a] < val[b];
}struct Node
{int l, r, id, lca, nxt, u, v, need_lca;Node(int _u, int _v, int _id, int _nxt){u = _u, v = _v, id = _id, nxt = _nxt;}Node(){}void init(){if(lca == u)l = st[lca], r = st[v], need_lca = 0;else if(lca == v)l = st[lca], r = st[u], need_lca = 0;else{if(st[u] < st[v]) l = et[u], r = st[v];else l = et[v], r = st[u];need_lca = 1;}return ;}
}node[MAXM];
int head_node[MAXM], cnt_node = 1;void insert_node(int u, int v, int id)
{node[++ cnt_node] = Node(u, v, id, head_node[u]), head_node[u] = cnt_node;node[++ cnt_node] = Node(v, u, id, head_node[v]), head_node[v] = cnt_node;
}int ans[MAXM];int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}int vis[MAXN];void dfs_tarjan(int x)
{vis[x] = 1;for(int pos = head[x];pos;pos = edge[pos].nxt){int v = edge[pos].v;if(vis[v]) continue;dfs_tarjan(v);int f1 = find(x), f2 = find(v);fa[f2] = f1;}for(int pos = head_node[x];pos;pos = node[pos].nxt){int v = node[pos].v;if(vis[v])node[pos].lca = node[pos ^ 1].lca = find(v);}
}void tarjan_lca()
{for(int i = 1;i <= n;++ i) fa[i] = i;dfs_tarjan(1);
}int size;int cmp2(Node& a, Node& b)
{return a.l/size == b.l/size ? a.r < b.r : a.l/size < b.l/size;
}int w[MAXN];void add(int x)
{if(w[x] == 0) tong[val[x]] += 1;else if(w[x] == 1) tong[val[x]] -= 1;if(tong[val[x]] == 1 && w[x] == 0) ++ sum;if(tong[val[x]] == 0 && w[x] == 1) -- sum; ++ w[x];
}void del(int x)
{if(w[x] == 1) tong[val[x]] -= 1;else if(w[x] == 2) tong[val[x]] += 1;if(tong[val[x]] == 1 && w[x] == 2) ++ sum;if(tong[val[x]] == 0 && w[x] == 1) -- sum;-- w[x];
}bool is_cal[MAXM << 1];int main()
{read(n), read(m);for(int i = 1;i <= n;++ i) read(val[i]), id[i] = i;for(int i = 1;i < n;++ i){int tmp1, tmp2;read(tmp1), read(tmp2);insert(tmp1, tmp2);}std::sort(id + 1, id + 1 + n, cmp);for(int i = 1, j = 1;i <= n;){num[j] = val[id[i]];while(val[id[i]] == num[j]) val[id[i]] = j, ++ i;++ j;}dfs(1);for(int i = 1;i <= m;++ i){int tmp1, tmp2;read(tmp1), read(tmp2);insert_node(tmp1, tmp2, i);}tarjan_lca();for(int i = 2;i <= cnt_node;++ i)node[i].init();size = sqrt(n);if(size == 0) size = 1;std::sort(node + 2, node + 1 + cnt_node, cmp2);int l = 1, r = 1;add(seq[1]);for(int i = 2;i <= cnt_node;++ i){if(is_cal[node[i].id]) continue;is_cal[node[i].id] = 1;while(l < node[i].l) del(seq[l]), ++ l;while(l > node[i].l) -- l, add(seq[l]);while(r < node[i].r) ++ r, add(seq[r]);while(r > node[i].r) del(seq[r]), -- r;if(node[i].need_lca) add(node[i].lca); ans[node[i].id] = sum;if(node[i].need_lca) del(node[i].lca); }for(int i = 1;i <= m;++ i)printf("%d\n", ans[i]);return 0;
} 

转载于:https://www.cnblogs.com/huibixiaoxing/p/11254289.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！