[题目链接]
http://codeforces.com/contest/1479/problem/D
[题解]
做法 (1) :
考虑树上莫队 ， 维护每种颜色的 (cnt) 数组 ， 直接用树状数组 / 线段树这样的带 (log) 数据结构会得到一个复杂度为 (O(N sqrt{N} log(N))) 的做法。 这样显然是不优的 ， 考虑均摊 ， 将线段树改为分块即可。这样的复杂度为 (O(Nsqrt{N}))
做法 (2) :
不妨给每种颜色分配一个 (2 ^ {64}) 以内的随机权值。 记 (f(u , l , r)) 表示从根节点到节点 (u) 路径上颜色种类在 ([l , r]) 区间内的点得权值异或和。 这可以用可持久化线段树轻松维护。 那么
条路径的权值异或和 (f(u , v , l , r)) 就可以通过四棵线段树异或出。
考虑二分求解 ， 若 (f(u , v , l , r) = 0) , 则退出。 否则在左子树 / 右子树中分别寻找答案。
这样对于一组询问的正确率为 (1 - 2 ^ {-64})。
那么 (q) 组询问的正确率至少是 :
(egin{aligned} Prleft[ igwedge_{i=1}^{q} A_i ight] & = 1 - Prleft[ igvee_{i=1}^q ar A_i ight] \ & geq 1 - sum_{i=1}^q Pr[ar A_i] \ & = 1 - sum_{i=1}^q left( 1 - Pr[A_i] ight) \ & geq 1 - sum_{i=1}^q left( 1 - left( 1 - 2^{-64} ight) ight) \ & = 1 - 2^{-64}q, end{aligned})
故正确率大于 (1 - 2 ^ {44})。 是足以通过这道题的。
时间复杂度 ： (O(NlogN))。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i , l , r) for (int i = (l); i < (r); ++i)
const int MN = 3e5 + 5 , MM = MN * 40;
typedef unsigned long long ull;
mt19937_64 get_value(355);
int N , M , fa[MN] , size , A[MN] , ans;
ull key[MM] , sum[MM];
int lc[MM] , rc[MM] , root[MM];
inline int query(int a , int b , int c , int d , int l , int r , int ql , int qr) {
if ((sum[a] ^ sum[b] ^ sum[c] ^ sum[d]) == 0) return -1;
if (l == r) return l;
int mid = l + r >> 1; int res = -1;
if (mid >= ql) {
res = query(lc[a] , lc[b] , lc[c] , lc[d] , l , mid , ql , qr);
if (res != -1) return res;
}
if (qr > mid) {
res = query(rc[a] , rc[b] , rc[c] , rc[d] , mid + 1 , r , ql , qr);
if (res != -1) return res;
}
return -1;
}
inline void add(int &now , int old , int l , int r , int x , ull val) {
now = ++size; lc[now] = lc[old] , rc[now] = rc[old];
sum[now] = sum[old] ^ val;
if (l == r) return;
int mid = l + r >> 1;
if (mid >= x) add(lc[now] , lc[old] , l , mid , x , val);
else add(rc[now] , rc[old] , mid + 1 , r , x , val);
}
struct Edge {
int to , nxt;
} E[MN << 1];
int tot , head[MN];
inline void AddEdge(int u , int v) {
E[++tot] = (Edge) {v , head[u]};
head[u] = tot;
}
int heavy[MN] , siz[MN] , dep[MN] , top[MN];
inline void dfs1(int x) {
add(root[x] , root[fa[x]] , 1 , N , A[x] , key[A[x]]);
siz[x] = 1;
for (int i = head[x]; i; i = E[i].nxt) {
int v = E[i].to; if (v == fa[x]) continue;
dep[v] = dep[x] + 1 , fa[v] = x , dfs1(v) , siz[x] += siz[v];
if (siz[v] > siz[heavy[x]]) heavy[x] = v;
}
}
inline void dfs2(int x) {
if (heavy[x]) top[heavy[x]] = top[x] , dfs2(heavy[x]);
for (int i = head[x]; i; i = E[i].nxt) {
int v = E[i].to; if (v == fa[x] || v == heavy[x]) continue;
top[v] = v , dfs2(v);
}
}
inline int lca(int u , int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u , v);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u , v);
return v;
}
int main() {
scanf("%d%d" , &N , &M);
for (int i = 1; i <= N; ++i) scanf("%d" , &A[i]) , key[i] = get_value();
for (int i = 1; i < N; ++i) {
int u , v; scanf("%d%d" , &u , &v);
AddEdge(u , v) , AddEdge(v , u);
}
dfs1(1); top[1] = 1; dfs2(1);
while (M--) {
int u , v , sl , sr; scanf("%d%d%d%d" , &u , &v , &sl , &sr);
int LCA = lca(u , v);
printf("%d
" , query(root[u] , root[v] , root[LCA] , root[fa[LCA]] , 1 , N , sl , sr));
}
return 0;
}