树的基本知识
树的存储
存储树的最常见的方式是使用一个邻接表来保存它的边集.
我们可以把树看做一个由 N 个点与 N-1 条边组成的无向连通图, 图中的无向边看做成对出现的有向边, 以 head 数组作为表头, ver 和 edge 数组分别存储边的终点和权值, next 数组模拟链表指针.
- #include <bits/stdc++.h>
- #define lowbit(x) x & (-x)
- #define INF ~0U>>1
- using namespace std;
- const int N = 25000 + 10;
- int f[N <<1], minf[N <<1], n, L, R;
- struct data {
- int a, b, c;
- }dat[N];
- inline int read() {
- int res = 0, flag = 1;
- char c = getchar();
- for(; !isdigit(c); c = getchar()) if(c == '-') flag = -1;
- for(; isdigit(c); c = getchar()) res = (res<<3) + (res<<1) + (c^48);
- return res * flag;
- }
- bool cmp(data x, data y) {
- return x.b < y.b;
- }
- void updata(int x) {
- for(; x <= n; x += lowbit(x)) {
- minf[x] = f[x];
- for(int i = 1; i < lowbit(x); i <<= 1) minf[x] = min(minf[x], minf[x - i]);
- }
- }
- int ask(int l, int r) {
- int ans = INF;
- while(l <= r) {
- ans = min(f[r], ans);
- r--;
- for(; r - lowbit(r)>= l; r -= lowbit(r)) ans = min(minf[r], ans);
- }
- return ans;
- }
- int main() {
- n = read(), L = read(), R = read();
- for(int i = 1; i <= n; i++) dat[i].a = read(), dat[i].b = read(), dat[i].c = read();
- memset(f, -0x3f, sizeof(f));
- f[L - 1] = minf[L - 1] = 0;
- sort(dat + 1, dat + n + 1, cmp);
- for(int i = 1; i <= n; i++) {
- f[dat[i].b] = ask(dat[i].a - 1, dat[i].b - 1) + dat[i].c;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2859927.html