首页 > 代码库 > SPOJ QTREE Query on a tree
SPOJ QTREE Query on a tree
题意:
给一颗n个点的树,有两种操作
CHANGE i ti : 把第i条边的权变为ti
QUERY a b : 问点a 到 点b 之间的边的最大权
思路:
树剖处理边权。
由于是边,所以只需要把边权处理到子节点上即可(查询的时候从节点2开始查询,或者把0处理成负无穷)
具体见代码:
1 const int maxn = 10000 + 10; 2 const int maxnode = maxn * 4; 3 4 //线段树部分 5 int set_value, qL, qR; 6 int maxv[maxnode]; 7 8 void update(int o, int L, int R) 9 { 10 if (qL <= L && R <= qR) 11 { 12 maxv[o] = set_value; 13 return; 14 } 15 int M = L + (R - L) / 2; 16 if (qL <= M) update(lson); 17 if (qR > M) update(rson); 18 maxv[o] = max(maxv[o*2], maxv[o*2+1]); 19 } 20 21 int query(int o, int L, int R) { 22 if (qL <= L && R <= qR) 23 { 24 return maxv[o]; 25 } 26 int M = L + (R - L) / 2; 27 int ret = -INF; 28 if (qL <= M) ret = max(ret, query(lson)); 29 if (qR > M) ret = max(ret, query(rson)); 30 return ret; 31 } 32 33 //树链剖分部分: 34 // 35 //u为连接的点,w为边权 36 struct Edge { int u, v, w; }; 37 vector<int> G[maxn]; 38 vector<Edge> e; 39 //往往是双向边 40 void add_edge(int u, int v, int w) 41 { 42 e.push_back((Edge){u, v, w}); 43 G[u].push_back(v); 44 G[v].push_back(u); 45 } 46 47 struct Node 48 { 49 int size, dep, son, top, fa, ti; 50 //依次表示第i个节点的: 51 //子节点数量,深度,所在链的顶端,重儿子,dfs序 52 } t[maxn]; 53 54 int dfs_clock;//DFS时间序列 55 56 void dfs1(int u, int pa, int depth)//第一次DFS,得到size,dep,fa以及son的数据 57 { 58 t[u].son = 0; //重儿子,为0表示没有重儿子 59 t[u].size = 1; //节点数量 60 t[u].dep = depth; 61 t[u].fa = pa; 62 for (int i = 0; i != G[u].size(); ++ i) 63 { 64 int v = G[u][i]; 65 if (v == pa) continue; 66 dfs1(v, u, depth + 1); 67 t[u].size += t[v].size; 68 if (t[v].size > t[t[u].son].size) t[u].son = v; 69 } 70 } 71 72 void dfs2(int u, int pa) // 得到时间戳等数据,u为当前节点,pa为父链顶端节点 73 { 74 t[u].ti = ++ dfs_clock; //u这个节点的时间戳是dfs_clock,dfs_clock下标是从1开始的,没有0! 75 t[u].top = pa; //top是u所在链的顶端 76 if (t[u].son != 0) dfs2(t[u].son, t[u].top); //如果节点有重儿子,那么依旧是以pa为链顶端的一条链 77 for (int i = 0; i != G[u].size(); ++ i) 78 { 79 int v = G[u][i]; 80 if (v == t[u].son || v == t[u].fa) continue;//重儿子或者父节点,则跳过 81 dfs2(v, v);//新的一条链 82 } 83 } 84 85 int n; 86 int lca(int x, int y)//更新x到y的之间所有的区间 87 { 88 int ret = -INF; 89 while (t[x].top != t[y].top) 90 { 91 if (t[t[x].top].dep < t[t[y].top].dep) swap(x,y); //x深 y浅 92 qL=t[t[x].top].ti; 93 qR=t[x].ti; 94 ret = max(ret, query(1, 2, n)); 95 x = t[t[x].top].fa; 96 } 97 if (t[x].dep > t[y].dep) swap(x, y);//x是上面一些的节点 98 if (x != y) 99 { 100 qL = t[x].ti + 1; 101 qR = t[y].ti; 102 ret = max(ret, query(1, 2, n)); 103 } 104 return ret; 105 } 106 107 108 void init() 109 { 110 memset(maxv, 0, sizeof(maxv)); 111 dfs_clock = 0; 112 scanf("%d", &n); 113 for (int i = 0; i <= n; i++) G[i].clear(); 114 e.clear(); 115 int u, v, w; 116 for (int i = 1; i < n; i++) 117 { 118 scanf("%d%d%d", &u, &v, &w); 119 add_edge(u, v, w); 120 } 121 } 122 123 void solve() 124 { 125 dfs1(1, 0, 1); 126 dfs2(1, 1); 127 128 for (int i = 1; i < n; i++) 129 { 130 set_value = http://www.mamicode.com/e[i-1].w; 131 if (t[e[i-1].u].dep < t[e[i-1].v].dep) 132 qL = qR = t[e[i-1].v].ti; 133 else 134 qL = qR = t[e[i-1].u].ti; 135 update(1, 2, n); 136 } 137 char op[10]; 138 int u, v; 139 while (true) 140 { 141 scanf("%s", op); 142 if (op[0] == ‘D‘) break; 143 scanf("%d%d", &u, &v); 144 if (op[0] == ‘Q‘) 145 { 146 printf("%d\n", lca(u, v)); 147 } 148 else 149 { 150 set_value =http://www.mamicode.com/ v; 151 if (t[e[u-1].u].dep < t[e[u-1].v].dep) 152 qL = qR = t[e[u-1].v].ti; 153 else 154 qL = qR = t[e[u-1].u].ti; 155 update(1, 2, n); 156 } 157 } 158 printf("\n"); 159 } 160 161 int main() 162 { 163 int T; 164 scanf("%d", &T); 165 while (T--) 166 { 167 init(); 168 solve(); 169 } 170 return 0; 171 }
SPOJ QTREE Query on a tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。