题目链接:http://poj.org/problem?id=2763

n个节点的树上知道了每条边权,然后有两种操作:0操作是输出 当前节点到 x节点的最短距离,并移动到 x 节点位置;1操作是第i条边的边权变成x。

树链边权剖分的模版题,修改单边权和求和。

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + ;
struct EDGE {
int next, to, cost;
}edge[MAXN << ];
int head[MAXN], tot;
int from[MAXN], to[MAXN], cost[MAXN];
int par[MAXN], dep[MAXN], son[MAXN], size[MAXN];
int top[MAXN], id[MAXN], cnt; void init() {
cnt = tot = ;
memset(head, -, sizeof(head));
} inline void add(int u, int v, int cost) {
edge[tot].next = head[u];
edge[tot].to = v;
head[u] = tot++;
} void dfs1(int u, int p, int d) {
dep[u] = d, par[u] = p, size[u] = , son[u] = u;
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs1(v, u, d + );
if(size[v] >= size[son[u]])
son[u] = v;
size[u] += size[v];
}
} void dfs2(int u, int p, int t) {
top[u] = t, id[u] = ++cnt;
if(son[u] != u)
dfs2(son[u], u, t);
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v == son[u] || v == p)
continue;
dfs2(v, u, v);
}
} struct segtree {
int l, r, val;
}T[MAXN << ]; void build(int p, int l, int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r;
if(l == r) {
return ;
}
build(p << , l, mid);
build((p << )|, mid + , r);
} void updata(int p, int pos, int num) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == T[p].r && T[p].l == pos) {
T[p].val = num;
return ;
}
if(pos <= mid) {
updata(p << , pos, num);
}
else {
updata((p << )|, pos, num);
}
T[p].val = T[p << ].val + T[(p << )|].val;
} int query(int p, int l, int r) {
int mid = (T[p].l + T[p].r) >> ;
if(l == T[p].l && T[p].r == r) {
return T[p].val;
}
if(r <= mid) {
return query(p << , l, r);
}
else if(l > mid) {
return query((p << )|, l, r);
}
else {
return query(p << , l, mid) + query((p << )|, mid + , r);
}
} int find(int u, int v) {
int fu = top[u], fv = top[v], res = ;
while(fv != fu) {
if(dep[fu] > dep[fv]) {
res += query(, id[fu], id[u]);
u = par[fu];
fu = top[u];
}
else {
res += query(, id[fv], id[v]);
v = par[fv];
fv = top[v];
}
}
if(v == u)
return res;
else if(dep[u] > dep[v])
return res + query(, id[son[v]], id[u]);
else
return res + query(, id[son[u]], id[v]);
} int main()
{
int n, m, root;
while(~scanf("%d %d %d", &n, &m, &root)) {
init();
for(int i = ; i < n; ++i) {
scanf("%d %d %d", from + i, to + i, cost + i);
add(from[i], to[i], cost[i]);
add(to[i], from[i], cost[i]);
}
dfs1(, , );
dfs2(, , );
build(, , cnt);
for(int i = ; i < n; ++i) {
if(dep[from[i]] < dep[to[i]])
swap(from[i], to[i]);
updata(, id[from[i]], cost[i]);
}
int op, pos, num;
while(m--) {
scanf("%d", &op);
if(op) {
scanf("%d %d", &pos, &num);
updata(, id[from[pos]], num);
}
else {
scanf("%d", &pos);
printf("%d\n", find(root, pos));
root = pos;
}
}
}
}

最新文章

  1. rake deploy ! [rejected] master -&gt; master (non-fast-forward) error: failed to push some refs to解决方法
  2. 项目管理-Kick OFF 简称KO
  3. Hibernate(五)__hql语句
  4. JavaScript对象属性赋值操作的逻辑
  5. 开发Android必知的工具
  6. 配置ssh免密码连接
  7. java 读取文件的字节数组
  8. iphone dev 入门实例6:How To Use UIScrollView to Scroll and Zoom and Page
  9. 【MySql】性能优化之分析命令
  10. Java 8 VM GC Tuning Guide Charter2
  11. 【Android - 框架】之GreenDao的使用
  12. HTML2列表表单框架
  13. 同时显示多个 Notification
  14. word页眉页脚 首页 索引 正文各不同的处理方法
  15. Jmeter接口测试实战-数据传递
  16. qcow2虚拟磁盘映像转化为vmdk
  17. 编程语言吐槽之Java与C
  18. beautiful number 数位dp
  19. css 渐变动画
  20. url后面带斜杠与不带斜杠的区别

热门文章

  1. HDU 1677
  2. 学军NOI训练13 T3 白黑树
  3. 实现窗口逐渐增大(moveTo(),resizeTo(),resizeBy()方法)
  4. Js获取日期时间及其它操作
  5. ionic cordova plugin for ios
  6. AI 状态机
  7. C语言深入学习系列 - 字节对齐&amp;内存管理
  8. HDU 1041 Computer Transformation
  9. VS2010开发2dx无法解析的外部符号解决记录
  10. JOB的创建,定时,执行