【题目来源】https://www.luogu.com.cn/problem/SP10707【题目描述】给定一棵包含 N 个节点的树节点编号从 1 到 N。每个节点都有一个整数点权。你需要回答若干组询问询问的形式如下u v求从节点 u 到节点 v 的简单路径上有多少种不同的点权。【输入格式】第一行包含两个整数 N 和 M。(N≤4×10^4, M≤10^5)第二行包含 N 个整数第 i 个整数表示第 i 个节点的点权。接下来的 N−1 行每行包含两个整数 u 和 v表示节点 u 和节点 v 之间存在一条树边。接下来的 M 行每行包含两个整数 u 和 v表示一组询问。【输出格式】对于每组询问输出一行一个整数表示对应询问的答案。【输入样例】8 2105 2 9 3 8 5 7 71 21 31 43 53 63 74 82 57 8【输出样例】44【数据范围】N≤4×10^4, M≤10^5。【算法分析】● 基础莫队算法https://blog.csdn.net/hnjzsyjyj/article/details/163114366● 本题如果测试数据点权极大必须增加离散化代码否则数组越界。vectorint v; for(int i1; in; i) v.push_back(val[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i1; in; i) { val[i]lower_bound(v.begin(),v.end(),val[i])-v.begin()1; }“离散化”代码参见https://blog.csdn.net/hnjzsyjyj/article/details/153268411● 树上莫队Tree Mos Algorithm是基础序列莫队在树形结构上的拓展算法。其核心思想是借助入栈出栈式欧拉括号序将整棵树序列化成长度为2n的一维数组从而将树上的路径查询与子树查询等价转化为该一维数组上的区间查询问题。​​​​​​​树上莫队算法的实现需要欧拉序、LCA 等前置知识。1欧拉序https://blog.csdn.net/hnjzsyjyj/article/details/1396812462LCAhttps://blog.csdn.net/hnjzsyjyj/article/details/152234376【算法代码】#include bits/stdc.h using namespace std; const int N4e44; const int M1e55; const int LOG18; vectorint g[N]; int in[N],out[N]; int dep[N],f[N][LOG]; bool vis[N]; int euler[N1]; int val[N],val_cnt[N]; int ans[M]; int tot,block; int cur; struct Node { int le,ri; int lca,id; } q[M]; void dfs_lca(int u,int fa) { f[u][0]fa; dep[u]dep[fa]1; for(int k1; kLOG; k) { f[u][k]f[f[u][k-1]][k-1]; } for(int t:g[u]) { if(t!fa) dfs_lca(t,u); } } int get_lca(int u,int v) { if(dep[u]dep[v]) swap(u,v); for(int iLOG-1; i0; i--) { if(dep[f[u][i]]dep[v]) uf[u][i]; } if(uv) return u; for(int iLOG-1; i0; i--) { if(f[u][i]!f[v][i]) { uf[u][i],vf[v][i]; } } return f[u][0]; } void dfs_euler(int u,int fa) { euler[tot]u; in[u]tot; for(int v:g[u]) { if(v!fa) dfs_euler(v,u); } euler[tot]u; out[u]tot; } bool cmp(Node a,Node b) { if(a.le/block ! b.le/block) { return a.leb.le; } //odd-even optimization if(a.le/block 1) return a.rib.ri; else return a.rib.ri; } void flip(int x) { int cval[x]; if(vis[x]) { val_cnt[c]--; if(val_cnt[c]0) cur--; } else { val_cnt[c]; if(val_cnt[c]1) cur; } vis[x]^1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cinnm; for(int i1; in; i) { cinval[i]; } /* - discretization - vectorint v; for(int i1; in; i) v.push_back(val[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i1; in; i) { val[i]lower_bound(v.begin(),v.end(),val[i])-v.begin()1; }*/ for(int i1; in; i) { int x,y; cinxy; g[x].push_back(y); g[y].push_back(x); } dfs_lca(1,0); dfs_euler(1,0); blocksqrt(tot); for(int i1; im; i) { int u,v; cinuv; int LCAget_lca(u,v); if(in[u]in[v]) swap(u,v); if(LCAu) { q[i] {in[u],in[v],0,i}; } else { q[i] {out[u],in[v],LCA,i}; } } sort(q1,qm1,cmp); memset(vis,0,sizeof vis); memset(val_cnt,0,sizeof val_cnt); cur0; int le1,ri0; for(int i1; im; i) { while(riq[i].ri) flip(euler[ri]); while(leq[i].le) flip(euler[--le]); while(riq[i].ri) flip(euler[ri--]); while(leq[i].le) flip(euler[le]); if(q[i].lca!0) { flip(q[i].lca); ans[q[i].id]cur; flip(q[i].lca); } else ans[q[i].id]cur; } for(int i1; im; i) { coutans[i]\n; } return 0; } /* in: 8 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 out: 4 4 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/152234376https://blog.csdn.net/hnjzsyjyj/article/details/163114366https://blog.csdn.net/hnjzsyjyj/article/details/153268411