问题描述:
给定有 n 个节点的树，每个节点有一种颜色。有 m 次查询，每次查询给出两个节点u、v，回答从 u 到 v 的路径上有多少个不同颜色的节点。
| 输入：第 1 行输入 n 和 m；第 2 行输入 n 个整数，第 i 个整数表示第个节点的颜色；下面 n – 1 行中，每行输入两个整数 u 和 v，表示一条边(u，v)；下面 m 行中，每行输入两个整数 u 和 v，表示一个查询，回答从节点 u 到 v 的路径上有多少个不同颜色的节点。 |
| 输出：对于每个查询，输出一个整数。 |
| 数据范围：1 ≤ n ≤ 4 × 104，1 ≤ m ≤ 105 |
| 输入样例 | 输出样例 |
| 15 Insert 26 abcdefghijklmnop qrstuv wxy Move 15 Delete 11 Move 5 Insert 1 ^ Next Insert 1 _ Next Next Insert 4 .\/. Get 4 Prev Insert 1 ^ Move 0 Get 22 | .\/. abcde^_^f.\/.ghijklmno |
树形结构路径问题
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=4e5+100;
typedef int LL;
struct Query{
LL l,r,ll,rr,lca;
LL id;
}q[100010];
bool vis[maxn];
LL a[maxn],b[maxn];
LL cnt[maxn];
LL answer[maxn];
LL sum=0;
//莫队部分
bool cmp(Query A,Query B){ //排序规则
if(A.ll!=B.ll){ //左区间排序
return A.ll<B.ll;
}
if(A.ll&1) return A.rr>B.rr; //奇偶优化
else return A.rr<B.rr;
}
void add(LL x){
cnt[a[x]]++;
if(cnt[a[x]]==1) sum++; //去重
}
void del(LL x){
cnt[a[x]]--;
if(cnt[a[x]]==0) sum--;
}
void cal(LL x){
//每个节点都有一个颜色
(!vis[x])?add(x):del(x); //未重复的节点添加，否则就删除
vis[x]^=1; //标记添加或删除节点
}
///树链剖分部分(求LCA)
LL times=0;
LL siz[maxn],top[maxn],dep[maxn],fa[maxn],son[maxn]; //以当前子树为根的子树大小、每条链的顶点、深度、记录父节点、深度较大的子节点
vector<LL>g[maxn];
LL numid[maxn*2],st[maxn],ed[maxn]; //欧拉序、序列元素开始下标、序列元素结束下标
void predfs(LL u,LL father){
siz[u]=1;dep[u]=dep[father]+1;
fa[u]=father;
st[u]=++times;
numid[times]=u;
for(LL i=0;i<g[u].size();i++){ //遍历相关的节点
LL v=g[u][i];
if(v==father) continue; //父节点跳过
predfs(v,u); //递归子节点
siz[u]+=siz[v]; //递归回来后，父节点添加子节点的子节点数量
if(siz[v]>siz[son[u]]){ //更新深度较大的子节点
son[u]=v;
}
}
ed[u]=++times;numid[times]=u; //欧拉序
}
void dfs(LL u,LL topx){
top[u]=topx; //写入重链顶点
if(!son[u]) return; //无子节点返回
dfs(son[u],topx); //递归top相同的子节点，
for(LL i=0;i<g[u].size();i++){ //遍历关联节点
LL v=g[u][i];
if(v==fa[u]||v==son[u]) continue; //跳过
dfs(v,v); //递归新的top
}
}
LL getLCA(LL u,LL v){
while(top[u]!=top[v]){ //寻找最近的公共祖先
if(dep[top[u]]<dep[top[v]]) swap(u,v); //比较深度，选top深度更大的
u=fa[top[u]]; //替换父节点
}
if(dep[u]>dep[v])
swap(u,v);
return u;
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false); //加快执行效率
LL n,m;cin>>n>>m; //输入n个数m次查询
for(LL i=1;i<=n;i++){ //录入数字
cin>>a[i];b[i]=a[i];
}
stable_sort(b+1,b+1+n); //排序
LL siz=unique(b+1,b+1+n)-b-1; //去重
for(LL i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+siz,a[i])-b; //离散化
}
for(LL i=1;i<n;i++){ //记录树
LL u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
predfs(1,0);
dfs(1,1);
LL block=sqrt(n*2); //树上莫队：出栈+入栈，块长比普通的莫队多一倍
for(LL i=1;i<=m;i++){ //查询
LL u,v;cin>>u>>v;
if(st[u]>st[v]) swap(u,v); //先被访问的放前面
LL LCA=getLCA(u,v);
//u和v在同一个子树内
if(LCA==u||LCA==v){
q[i].id=i;
q[i].l=st[u];q[i].r=st[v];
q[i].ll=(st[u]-1)/block+1; //l端点分到的块的编号
q[i].rr=(st[v]-1)/block+1; //r端点分到的块的编号
q[i].lca=0;
}
//u和v不在同一棵子树内
else{
q[i].id=i;
q[i].l=ed[u];q[i].r=st[v];
q[i].ll=(ed[u]-1)/block+1;q[i].rr=(st[v]-1)/block+1;
q[i].lca=LCA; //最后要加上LCA的贡献
}
}
LL L=1;LL R=0;
sort(q+1,q+1+m,cmp);
for(LL i=1;i<=m;i++){
while(L<q[i].l) cal(numid[L++]); //该树的节点
while(L>q[i].l) cal(numid[--L]);
while(R<q[i].r) cal(numid[++R]);
while(R>q[i].r) cal(numid[R--]);
if(q[i].lca){ //加上公共父节点
cal(q[i].lca);
}
answer[q[i].id]=sum;
if(q[i].lca){ //去掉公共父节点
cal(q[i].lca);
}
}
for(LL i=1;i<=m;i++){ //输出结果
cout<<answer[i]<<endl;
}
return 0;
}
笔记：通过“欧拉序”把整棵树按照dfs的遍历顺序转化成了一维数组，vis记录查询路径的节点，入栈+1出栈-1，lca记录公共的祖先，如果是同一条重链上的公共祖先已经记录，如果不是就加上公共祖先再输出。
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/110251080