东莞市建设网站,网站友情链接形式,浏览器网站有哪些,安卓应用商店下载题意#xff1a; 给\(n(1 \leq n \leq 10^5)\)一棵树#xff0c;每个点有个权值。 还有\(m(1 \leq m \leq 10^5)\)个询问#xff1a;\(u \, v \, k\)#xff0c;查询路径\(u \to v\)上权值第\(k\)小的权值。 分析#xff1a; 和普通的区间一样#xff0c;对于树维护到根节…题意 给\(n(1 \leq n \leq 10^5)\)一棵树每个点有个权值。 还有\(m(1 \leq m \leq 10^5)\)个询问\(u \, v \, k\)查询路径\(u \to v\)上权值第\(k\)小的权值。 分析 和普通的区间一样对于树维护到根节点的路径信息父亲节点代表的树就是它的前一棵树。 查询的时候还要求出\(LCA(u,v)\)路径上的点数就是 \(u\)到根的个数\(v\)到根的个数-\(lca\)到根的个数\(\times 2\)如果\(lca\)的权值也在统计范围内统计个数再加\(1\)。 #include cstdio
#include cstring
#include algorithm
using namespace std;const int maxn 100000 10;struct Edge
{int v, nxt;Edge() {}Edge(int v, int nxt): v(v), nxt(nxt) {}
};int head[maxn], ecnt;
Edge edges[maxn * 2];void AddEdge(int u, int v) {edges[ecnt] Edge(v, head[u]);head[u] ecnt;
}int fa[maxn], L[maxn];void dfs(int u) {for(int i head[u]; ~i; i edges[i].nxt) {int v edges[i].v;if(v fa[u]) continue;fa[v] u;L[v] L[u] 1;dfs(v);}
}int n, m;int anc[maxn][20];void preprocess() {memset(anc, 0, sizeof(anc));for(int i 1; i n; i) anc[i][0] fa[i];for(int j 1; (1 j) n; j)for(int i 1; i n; i) if(anc[i][j-1])anc[i][j] anc[anc[i][j-1]][j-1];
}int LCA(int u, int v) {if(L[u] L[v]) swap(u, v);int log;for(log 0; (1 log) L[u]; log);for(int i log; i 0; i--)if(L[u] - (1i) L[v]) u anc[u][i];if(u v) return u;for(int i log; i 0; i--)if(anc[u][i] anc[u][i] ! anc[v][i])u anc[u][i], v anc[v][i];return fa[u];
}int a[maxn], b[maxn], tot;struct Node
{int lch, rch, sum;
};int sz;
Node T[maxn 5];
int root[maxn];int newnode() {sz;T[sz].lch T[sz].rch T[sz].sum 0;return sz;
}int update(int pre, int L, int R, int p) {int rt newnode();T[rt].lch T[pre].lch;T[rt].rch T[pre].rch;T[rt].sum T[pre].sum 1;if(L R) return rt;int M (L R) / 2;if(p M) T[rt].lch update(T[pre].lch, L, M, p);else T[rt].rch update(T[pre].rch, M1, R, p);return rt;
}void dfs2(int u) {root[u] update(root[fa[u]], 1, tot, a[u]);for(int i head[u]; ~i; i edges[i].nxt) {int v edges[i].v;if(v fa[u]) continue;dfs2(v);}
}int tmp;int query(int u, int v, int l, int L, int R, int k) {if(L R) return L;int M (L R) / 2;int sum T[T[u].lch].sum T[T[v].lch].sum - T[T[l].lch].sum * 2;if(L tmp tmp M) sum;if(sum k) return query(T[u].lch, T[v].lch, T[l].lch, L, M, k);else return query(T[u].rch, T[v].rch, T[l].rch, M1, R, k - sum);
}int main()
{scanf(%d%d, n, m);for(int i 1; i n; i) {scanf(%d, a i);b[i] a[i];}ecnt 0;memset(head, -1, sizeof(head));for(int i 1; i n; i) {int u, v; scanf(%d%d, u, v);AddEdge(u, v); AddEdge(v, u);}dfs(1);preprocess();sort(b 1, b 1 n);tot unique(b 1, b 1 n) - b - 1;for(int i 1; i n; i)a[i] lower_bound(b 1, b 1 tot, a[i]) - b;dfs2(1);while(m--) {int u, v, k; scanf(%d%d%d, u, v, k);int lca LCA(u, v);tmp a[lca];int ans query(root[u], root[v], root[lca], 1, tot, k);printf(%d\n, b[ans]);}return 0;
} 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/5285890.html
