查询树点对间不同数字的个数。
为什么我的程序越改越慢。。。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
const int N = 40005, M = 100005, K = 16;
int block[M];
struct Query { int l, r, i; } q[M];
bool operator <(const Query &a, const Query &b) {
return block[a.l] == block[b.l] ? a.r < b.r : a.l < b.l;
}
int v[M], p[M], h[N], cnt;
void add(int x, int y) { v[++cnt] = y, p[cnt] = h[x], h[x] = cnt; }
int beg[N], end[N], dfn[M], dep[N], fa[N][20], id[N], ID, ts;
void dfs(int x, int f) {
int i;
id[x] = ++ID; dfn[beg[x] = ++ts] = x; dep[x] = dep[f] + 1;
fa[x][0] = f;
FOR(i,1,K) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (i = h[x]; i; i = p[i]) if (v[i] != f) dfs(v[i], x);
dfn[end[x] = ++ts] = x;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int t = dep[x] - dep[y], i;
for (i = 0; i <= K; ++i)
if ((1 << i) & t) x = fa[x][i];
for (i = K; i >= 0; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return x == y ? x : fa[x][0];
}
int now, vis[N], sum[N], a[N], b[N], ans[M];
void modify(int x) {
if (vis[x]) { if (!--sum[a[x]]) --now; }
else { if (!sum[a[x]]++) ++now; }
vis[x] = !vis[x];
}
void transform(int &l, int &r, int &ans, int ql, int qr) {
while (r < qr) modify(dfn[++r]);
while (r > qr) modify(dfn[r--]);
while (l < ql) modify(dfn[l++]);
while (l > ql) modify(dfn[--l]);
int x = dfn[l], y = dfn[r];
int t = lca(x, y);
if (t != x && t != y) modify(t);
ans = now;
if (t != x && t != y) modify(t);
}
int main() {
int n, m, x, y, i, sz, t, l = 1, r = 0;
scanf("%d%d", &n, &m);
FOR(i,1,n) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
FOR(i,1,n) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
FOR(i,2,n) scanf("%d%d", &x, &y), add(x, y), add(y, x);
dfs(1, 1); sz = sqrt(ts);
FOR(i,1,ts) block[i] = (i - 1) / sz + 1;
FOR(i,1,m) {
scanf("%d%d", &x, &y);
if (id[x] > id[y]) swap(x, y);
q[i] = (Query) { lca(x, y) == x ? beg[x] : end[x], beg[y], i };
}
sort(q + 1, q + m + 1);
FOR(i,1,m) transform(l, r, ans[q[i].i], q[i].l, q[i].r);
FOR(i,1,m) printf("%d\n", ans[i]);
return 0;
}COT2 - Count on a tree II
no tags
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.
Example
Input:
8 58 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8
Output:
4
4