hdu 5111 树上求交(树链剖分 + 主席树)
题意：
给出两棵树,大小分别为(n1),(n2), 树上的结点权值为(weight_i)
同一棵树上的结点权值各不相同，不同树上的结点权值可以出现重复
每次查询 (u1) (v1) (u2) (v2)
第一棵树上(u1) 到 (v1)的路径上所有结点权值组成的集合(S1)
第二棵树上(u2) 到 (v2)的路径上所有结点权值组成的集合(S2)
求(S1) 与 (S2) 的交集
(1 <= n1,n2 <= 10^{5})
(q <= 50000)
(0 <= weight_i <= 10^{9})
(1 <= u1,v1 <= n1, 1 <= u2,v2 <= n2)
思路：题解
先考虑序列上的问题
将第二个序列的权值映射为相同权值在第一个序列中出现的下标
那么对于(L1,R1,L2,R2)来说
就是查询第二个序列中区间([L2,R2])权值在([L1,R1])的数字个数
这是经典问题，可以用主席树解决
现在考虑树上问题，
路径映射到区间是不连续的，用树链剖分处理，每段都是连续的，就可以用主席树来查询
主席树查询也是要求连续的，如果同样用树链剖分来处理复杂度有3个log了
由于不带修改，如果用dfs序的方式建主席树
就可以用root[u],root[v],root[lca]这些根的信息来处理表示u到v上的所有路径信息了
这样复杂度就变成两个log了
ps: 码力太弱了，写不动，写了大概两个半小时才写完，中间顺带复习了一波树链剖分
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define ls(i) seg[i].lc
#define rs(i) seg[i].rc
using namespace std;
namespace IO {
const int MX = 4e7; //1e7 占用内存 11000kb
char buf[MX]; int c, sz;
void begin() {
c = 0;
sz = fread(buf, 1, MX, stdin);//一次性全部读入
}
inline bool read(int &t) {
while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
if (c >= sz) return false;//若读完整个缓冲块则退出
bool flag = 0; if(buf[c] == '-') flag = 1, c++;
for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
if(flag) t = -t;
return true;
}
}
void read(int &x){
x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
}
const int N = 1e5 + 10;
int n1,n2,x;
int value2[N];
map<int,int> pos;
struct Edge{int v,nxt;};
///主席树部分
struct T{
int lc,rc,cnt;
}seg[N * 50];
int root[N],tot;
void seg_init(){
root[0] = tot = 0;
seg[0].lc = seg[0].rc = seg[0].cnt = 0;
}
void update(int &rt,int l,int r,int v){
seg[++tot] = seg[rt];
rt = tot;
seg[rt].cnt++;
if(l >= r) return ;
int m = l + r>>1;
if(v <= m) update(ls(rt),l,m,v);
else update(rs(rt),m+1,r,v);
}
int query(int rt1,int rt2,int rt3,int l,int r,int pos){
if(r <= pos) return seg[rt1].cnt + seg[rt2].cnt - 2 * seg[rt3].cnt;
if(l > pos) return 0;
int m = l + r >>1;
return query(ls(rt1),ls(rt2),ls(rt3),l,m,pos) + query(rs(rt1),rs(rt2),rs(rt3),m+1,r,pos);
}
int calc(int rt1,int rt2,int rt3,int L,int R){
return query(rt1,rt2,rt3,1,n1,R) - query(rt1,rt2,rt3,1,n1,L-1);
}
///dfs插入部分
Edge e[2 * N];
int head[N],EN;
int dep[N];
int fa[N][25];
void edge_init(){
EN = 0;
memset(head,-1,sizeof(head));
}
void add(int u,int v){
e[EN].v = v,e[EN].nxt = head[u];
head[u] = EN++;
}
void dfs(int u,int f,int d){
dep[u] = d,fa[u][0] = f;
root[u] = root[f];
if(value2[u]) update(root[u],1,n1,value2[u]);
for(int i = 1;i <= 20;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
for(int i = head[u];~i;i = e[i].nxt){
int v = e[i].v;
if(v != f) dfs(v, u, d + 1);
}
}
int lca(int u,int v){
if(dep[u] < dep[v]) swap(u,v);
int d = dep[u] - dep[v];
for(int i = 20;i >= 0 && u != v;i--) if(d & (1<<i)) u = fa[u][i];
if(u == v) return u;
for(int i = 20;i >= 0;i--) if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
return fa[u][0];
}
struct HLD{///树链剖分处理
int siz[N],dep[N],fa[N];
int top[N];///u所在链的第一个结点
int son[N];///以u为根的重儿子
int r[N];///每个位置是什么结点
int w[N];///结点u在哪个位置
int z;
int head[N],EN;
Edge e[2 * N];
void add(int u,int v){
e[EN].v = v,e[EN].nxt = head[u];
head[u] = EN++;
}
void init(){
EN = z = dep[1] = 0;
memset(head,-1,sizeof(head));
}
void dfs(int u,int f,int d){
fa[u] = f,dep[u] = d;
siz[u] = 1,son[u] = 0;
for(int i = head[u];~i;i = e[i].nxt){
int v = e[i].v;
if(v!=f){
dfs(v,u,d+1);
if(siz[v] > siz[son[u]]) son[u] = v;
siz[u] += siz[v];
}
}
}
void build(int u,int tp,int f){///当前结点所在链的第一个结点
w[u] = ++z,r[z] = u,top[u] = tp;
if(son[u]) build(son[u],tp,u);
for(int i = head[u];~i;i = e[i].nxt){
if(e[i].v != f && e[i].v != son[u]) build(e[i].v,e[i].v,u);
}
}
int solve(int u,int v,int c,int d){
int cd = lca(c,d);
int ans = 0;
int f1 = top[u],f2 = top[v];
while(f1 != f2){
if(dep[f1] < dep[f2]) swap(f1,f2),swap(u,v);
ans += calc(root[c],root[d],root[cd],w[f1],w[u]);
if(value2[cd] >= w[f1] && value2[cd] <= w[u]) ans++;
u = fa[f1],f1 = top[u];
}
if(dep[u] > dep[v]) swap(u,v);
ans += calc(root[c],root[d],root[cd],w[u],w[v]);
if(value2[cd] >= w[u] && value2[cd] <= w[v]) ans++;
return ans;
}
}hld;
void init(){
edge_init();
hld.init();
seg_init();
pos.clear();
}
int main(){
IO::begin();
while(IO::read(n1)){
init();
for(int i = 2;i <= n1;i++){
IO::read(x);
hld.add(x,i);
}
hld.dfs(1,0,0);
hld.build(1,1,0);
for(int i = 1;i <= n1;i++) {
IO::read(x);
pos[x] = i;
}
IO::read(n2);
for(int i = 2;i <= n2;i++){
IO::read(x);
add(x,i);
}
for(int i = 1;i <= n2;i++) {
IO::read(x);
if(pos[x]) value2[i] = hld.w[pos[x]];
else value2[i] = 0;
}
dfs(1,0,0);
int a,b,c,d,q;
IO::read(q);
while(q--){
IO::read(a),IO::read(b),IO::read(c),IO::read(d);
printf("%d
",hld.solve(a,b,c,d));
}
}
return 0;
}