实验对象——2013 noip day1 T3
本来可以直接用倍增lca解决。。但是我比较的扯淡。。所以用树链剖分来搞
和普通点权不同的是,对于一颗树来说,每一个点的点权被定义为他的父亲到他的边权,所以与一般的树链剖分相比,最后统一到一条链上时,线段树维护的一边端点要加1。。其他的就没了。然后注意往上跳的时候的比较时dep[un[a]] 和 dep[un[b]] 不是dep[a] dep[b];
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxe = 100001; const int maxn = 100010; const int inf = 0x3f3f3f3f; struct line { int l, r, d; }s[maxe]; struct edge { int t, d; edge* next; }e[maxn * 2], *head[maxn]; int ne = 0; void addedge(int f, int t, int d) { e[ne].t = t, e[ne].d = d, e[ne].next = head[f], head[f] = e + ne ++; } int int_get() { char c; int x = 0; c = (char)getchar(); while(!isdigit(c)) c = (char)getchar(); while(isdigit(c)) { x = x * 10 + (int)(c - ‘0‘); c = (char)getchar(); } return x; } int n, m; int father[maxn]; int find(int x) { return x == father[x] ? x : find(father[x]); } bool cmp(line a, line b) { return a.d > b.d; } int h[maxn], fa[maxn], un[maxn], map[maxn]; int w[maxn]; int size[maxn]; struct node { int key; node* l, *r; }se[maxn * 3], *root; int ns = 0; node* build(int l, int r) { node* now = se + ns ++; if(l ^ r) { int mid = (l + r) >> 1; now-> l = build(l, mid); now-> r = build(mid + 1, r); } return now; } void update(node* x) { if(x-> l) x-> key = min(x-> l-> key, x-> r-> key); } void insert(node* now, int l, int r, int pos, int v) { if(l == r) now-> key = v; else { int mid = (l + r) >> 1; if(pos <= mid) insert(now-> l, l, mid, pos, v); else insert(now-> r, mid + 1, r, pos, v); update(now); } } int _query(node* now, int l, int r, int ls, int rs) { if(l == ls && r == rs) return now-> key; else { int mid = (l + r) >> 1; if(rs <= mid) return _query(now-> l, l, mid, ls, rs); else if(ls >= mid + 1) return _query(now-> r, mid + 1, r, ls, rs); else return min(_query(now-> l, l, mid, ls, mid), _query(now-> r, mid + 1, r, mid + 1, rs)); } } void dfs(int x, int pre) { if(pre == -1) { h[x] = 1, fa[x] = x; w[x] = inf; } else h[x] = h[pre] + 1, fa[x] = pre; size[x] = 1; for(edge* p = head[x]; p; p = p-> next) { if(!h[p-> t]) { dfs(p-> t, x); w[p-> t] = p-> d; size[x] += size[p-> t]; } } } int tot = 0; void _union(int x, int pre) { if(pre == -1) un[x] = x; else un[x] = pre; map[x] = ++ tot; insert(root, 1, n, map[x], w[x]); int smax = 0; int pos = 0; for(edge* p = head[x]; p; p = p-> next) { if(h[p-> t] > h[x]) { if(size[p-> t] > smax) smax = size[p-> t], pos = p-> t; } } if(!smax) return; else { _union(pos, un[x]); for(edge* p = head[x]; p; p = p-> next) { if(h[p-> t] > h[x] && p-> t != pos) { _union(p-> t, -1); } } } } void pre() { for(int i = 1; i <= n; ++ i) father[i] = i; sort(s + 1, s + 1 + m, cmp); int cnt = 0; for(int i = 1; i <= m && cnt <= n; ++ i) { int fx = find(s[i].l); int fy = find(s[i].r); if(fx != fy) { father[fy] = fx; ++ cnt; addedge(s[i].l, s[i].r, s[i].d); addedge(s[i].r, s[i].l, s[i].d); } } } void read() { n = int_get(), m = int_get(); for(int i = 1; i <= m; ++ i) { s[i].l = int_get(); s[i].r = int_get(); s[i].d = int_get(); } root = build(1, n); } int Q = 0; int query(int a, int b) { if(find(a) != find(b)) return -1; int ret = inf; while(un[a] != un[b]) { if(h[un[a]] > h[un[b]]) { int rs= map[a], ls = map[un[a]]; if(ls > rs) {a = fa[un[a]]; continue;} ret = min(ret, _query(root, 1, n, ls, rs)); a = fa[un[a]]; } else { int rs = map[b], ls = map[un[b]]; if(ls > rs) {b = fa[un[b]]; continue;} ret = min(ret, _query(root, 1, n, ls, rs)); b = fa[un[b]]; } } if(a != b) { if(h[a] < h[b]) swap(a, b); int rs = map[a], ls = map[b] + 1; if(ls <= rs) { ret = min(ret, _query(root, 1, n, ls, rs)); } } return ret; } void sov() { pre(); for(int i = 1; i <= n; ++ i) { if(!h[i]) { dfs(i, -1); _union(i, -1); } } Q = int_get(); while(Q --) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", query(l, r)); } } int main() { //freopen("test.in", "r", stdin); read(); sov(); return 0; }
原文:http://www.cnblogs.com/ianaesthetic/p/3873053.html