首页 > 代码库 > SPOJ-Qtree-树链剖分（边的剖分）
SPOJ-Qtree-树链剖分（边的剖分）
【前言】TTvTT先让我呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜一下。。。。。。经历了5发WA，6发RE，3发TLE后，今天终于和这道题做了个了断了。
题意：一棵树，给出边权值，有两种操作：更改一条边的值；查找a到b路径上的最大边权值。
【唧唧喳喳】这道题算是树链剖分对边剖分的一道很好的训练题吧，但是数据好像比较变态很容易TLE的样子，嘛啊，其实我也布吉岛。
【思路】： 对于一棵树，每个节点（除了根节点）都只有一个父亲，那么对于每条边，做儿子的那个节点用来记录边权值。大体就是这样。TvT然后查询的时候，注意和点的剖分的不同的是，查询的时候比较的是链首节点的深度，因为边的剖分不同于点的剖分，比较深度的点存的是与其父节点的连边，所以如果比较最下面的节点，当来到LCA的时候就会往上走多了一个不必走的节点，会出错。
【总结】：开始用map存节点来对应边，但是TLE了，然后改成用了pre和fun1来对应输入的各边和输入的节点的关系，用tree和fun2对应编号节点和编号。这才过了。
AC代码（420ms）：
【布吉岛是不是数据变弱了，我用420ms才过，看有些菊苣用了2.6s_(:з」∠)_】
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <climits> 5 using namespace std; 6 int const maxn = 10009; 7 int pre[maxn], n, edge, cnt, fa[maxn], deep[maxn], num[maxn], son[maxn], tree[maxn], fun1[maxn], fun2[maxn]; 8 int to[maxn<<1], next[maxn<<1], head[maxn], top[maxn], seq[maxn<<1], cost[maxn]; 9 void add(int u, int v, int num) 10 { 11 to[edge] = v; 12 next[edge] = head[u]; 13 seq[edge] = num; 14 head[u] = edge++; 15 } 16 void init() 17 { 18 scanf("%d", &n); 19 memset(head, -1, sizeof(head)); 20 memset(son, -1, sizeof(son)); 21 edge = cnt = 0; 22 for(int i = 1; i < n; i++) { 23 int a, b; scanf("%d%d%d", &a, &b, &cost[i]); 24 add(a, b, i); add(b, a, i); 25 } 26 fa[1] = deep[1] = tree[1] = 1; 27 } 28 void dfs1(int u) 29 { 30 num[u] = 1; 31 for(int e = head[u]; ~e; e = next[e]) { 32 int too = to[e]; 33 if(fa[u] != too) { 34 pre[seq[e]] = too; //把输入的边和较深的节点对应起来 35 fun1[too] = seq[e]; //存节点对应的边 36 deep[too] = deep[u]+1; 37 fa[too] = u; 38 dfs1(too); num[u] += num[too]; 39 if(son[u] == -1||num[son[u]] < num[too]) son[u] = too; 40 } 41 } 42 } 43 void dfs2(int u, int lead) 44 { 45 top[u] = lead; 46 if(u != 1) tree[u] = ++cnt, fun2[cnt] = u; //剖分的编号一一对应 47 if(son[u] == -1) return; 48 dfs2(son[u], lead); 49 for(int e = head[u]; ~e; e = next[e]) { 50 int too = to[e]; 51 if(fa[u] != too && son[u] != too) dfs2(too, too); 52 } 53 } 54 #define lson l, m, rt<<1 55 #define rson m+1, r, rt<<1|1 56 int sgt[maxn<<2] = {INT_MIN}; 57 void push_up(int rt) 58 { 59 sgt[rt] = max(sgt[rt<<1], sgt[rt<<1|1]); 60 } 61 void build(int l, int r, int rt) 62 { 63 if(l == r) { 64 int pos = fun1[fun2[l]]; 65 sgt[rt] = cost[pos]; return; 66 } 67 int m = (l+r)>>1; 68 build(lson); build(rson); 69 push_up(rt); 70 } 71 void change(int l, int r, int rt, int pos, int val) 72 { 73 if(l == r) { sgt[rt] = val; return; } 74 int m = (l+r)>>1; 75 if(pos <= m) change(lson, pos, val); 76 if(m < pos) change(rson, pos, val); 77 push_up(rt); 78 } 79 int query(int l, int r, int rt, int L, int R) 80 { 81 if(L <= l && r <= R) return sgt[rt]; 82 int m = (l+r)>>1; 83 int a, b; a = b = INT_MIN; 84 if(L <= m) a = query(lson, L, R); 85 if(m < R) b = query(rson, L, R); 86 return max(a, b); 87 } 88 int answer(int a, int b) 89 { 90 if(a == b) return 0; 91 int ans = INT_MIN; 92 while(top[a] != top[b]) { 93 if(deep[top[a]] < deep[top[b]]) swap(a, b); 94 ans = max(ans, query(1, n-1, 1, tree[top[a]], tree[a])); 95 a = fa[top[a]]; 96 } 97 if(deep[a] > deep[b]) swap(a, b); 98 if(a != b) ans = max(ans, query(1, n-1, 1, tree[son[a]], tree[b])); 99 return ans;100 }101 void work()102 {103 init();104 dfs1(1); dfs2(1, 1); build(1, n-1, 1);105 char s[20];106 while(scanf("%s", s) && s[0] != ‘D‘) {107 int a, b; scanf("%d%d", &a, &b);108 if(s[0] == ‘C‘) {109 change(1, n-1, 1, tree[pre[a]], b);110 }111 else {112 printf("%d\n", answer(a, b));113 }114 }115 }116 int main()117 {118 int t; cin>>t;119 while(t--) work();120 return 0;121 }
SPOJ-Qtree-树链剖分（边的剖分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。