3634.树
题解
在暴力做法中,我们需要依次比较所有颜色,这没有什么好的优化方式,考虑哈希。
我们给每个 ci 随机一个权值 wi,把答案拆成四条到根的链,定义他们的权值为 ∑ciwi,直接维护可持久化权值线段树,在八颗主席树上二分找到第一个不一样的地方即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <random>
using namespace std;
typedef unsigned long long ULL;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , out[SIZE] , *p1=in , *p2=in , *p3=out;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#define flush() (fwrite(out,1,p3-out,stdout) , p3=out)
#define putchar(c) (p3==out+SIZE && flush() , *p3 ++ = c)
class Flush{public: ~Flush(){flush();} } ___;
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(int x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[30] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef flush
#undef putchar
#undef SIZE
#endif
} using namespace IO;
const int N = 3e5+10 , M = N*2;
struct Node {
int l , r;
ULL sum;
};
int n , m;
int c[N];
int h[N] , e[M] , ne[M] , idx;
int f[20][N] , dep[N];
ULL w[N];
Node tr[N*24]; int root[N] , tridx;
mt19937_64 rng;
void add(int a , int b) {
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
int build(int l , int r) {
int u = ++ tridx;
tr[u].sum = 0;
if(l == r) return u;
int mid = (l+r) >> 1;
tr[u].l = build(l , mid);
tr[u].r = build(mid+1 , r);
return u;
}
int insert(int p , int l , int r , int x , ULL v) {
int u = ++ tridx;
tr[u] = tr[p]; tr[u].sum += v;
if(l == r) return u;
int mid = (l+r) >> 1;
if(x <= mid) tr[u].l = insert(tr[p].l , l , mid , x , v);
else tr[u].r = insert(tr[p].r , mid+1 , r , x , v);
return u;
}
void dfs(int u , int fa) {
f[0][u] = fa; dep[u] = dep[fa]+1;
root[u] = insert(root[fa] , 1 , n , c[u] , w[c[u]]);
for(int i = 1 ; i < 20 ; i ++)
f[i][u] = f[i-1][f[i-1][u]];
for(int i = h[u] ; ~i ; i = ne[i])
if(e[i] != fa) dfs(e[i] , u);
}
int LCA(int a , int b) {
if(a == b) return a;
if(dep[a] < dep[b]) swap(a , b);
for(int i = 19 ; i >= 0 ; i --) {
if(dep[f[i][a]] >= dep[b]) {
a = f[i][a];
}
}
if(a == b) return a;
for(int i = 19 ; i >= 0 ; i --) {
if(f[i][a] != f[i][b]) {
a = f[i][a]; b = f[i][b];
}
}
return f[0][a];
}
int query(int u1 , int u2 , int u3 , int u4 , int v1 , int v2 , int v3 , int v4 , int l , int r) {
ULL sum = tr[u1].sum + tr[u2].sum + tr[u3].sum + tr[u4].sum - tr[v1].sum - tr[v2].sum - tr[v3].sum - tr[v4].sum;
if(!sum) return n+1;
if(l == r) return l;
int mid = (l+r) >> 1;
int t = query(tr[u1].l , tr[u2].l , tr[u3].l , tr[u4].l , tr[v1].l , tr[v2].l , tr[v3].l , tr[v4].l , l , mid);
if(t <= n) return t;
return query(tr[u1].r , tr[u2].r , tr[u3].r , tr[u4].r , tr[v1].r , tr[v2].r , tr[v3].r , tr[v4].r , mid+1 , r);
}
int main() {
n = read();
memset(h , -1 , sizeof h);
for(int i = 1 ; i < n ; i ++) {
int a = read() , b = read();
add(a , b); add(b , a);
}
rng = mt19937_64(random_device{}());
for(int i = 1 ; i <= n ; i ++)
c[i] = read() , w[i] = rng();
root[0] = build(1 , n);
dfs(1 , 0);
m = read();
while(m --) {
int u1 = read() , v1 = read() , u2 = read() , v2 = read();
int lca1 = LCA(u1 , v1) , lca2 = LCA(u2 , v2);
write(query(root[u1] , root[v1] , root[lca2] , root[f[0][lca2]] ,
root[u2] , root[v2] , root[lca1] , root[f[0][lca1]] , 1 , n)-1);
}
return 0;
}