Housewife Wind--树链剖分

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

题目大意

有n个点，n-1条边，给出起始点s，q次操作，0 u，表示询问从s到u的路径权值之和，并且把s变为u，1 u val，表示把第u条边的权值改为val。

分析

重儿子：如果size[u]为v的子节点中size值最大的，那么u就是v的重儿子。 
轻儿子：v的除重儿子以外的子节点。 
重边：点v与其重儿子的连边。 
轻边：点v与其轻儿子的连边。 
重链：由重边连成的路径。 
轻链：轻边。

fa[x]：节点x的父节点。

dep[x]：节点x的深度（根节点深度为1）。

size[x]：节点x子树的节点之和。

son[x]：x的重儿子。

top[x]：x所在重链的顶端节点，如果是轻边，top[x] = x。

id[x]：x与其父节点的连边在线段树中的位置。

value[x]：将某条边的权值赋给两端节点中，深度大的节点，为什么要赋给深度大的呢？因为每个点要存的是其与父节点连边的权值。

num[x]：与dfs序作用相同。

head[x]：邻接表。

dfs1是找出fa，dep，size，son。

dfs2是找出top，id，num。

其他看代码注释吧。

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e5+5;
int n, q, s, cnt, tot;
int fa[N], dep[N], size[N], son[N], top[N], id[N], value[N], num[N], head[2*N];
struct Edge{int to, nxt;
}edge[2*N];
struct node{int l, r, sum;
}tr[N<<2];
struct Path{	//记录每条边的信息 int x, y, val;void read(){scanf("%d %d %d", &x, &y, &val);}
}path[N];
void add(int a, int b)
{edge[cnt].to = b;edge[cnt].nxt = head[a];head[a] = cnt++;
}
void dfs1(int d, int f, int u)//d:深度，f:父节点，u:当前节点 
{size[u] = 1;dep[u] = d;fa[u] = f;son[u] = 0;for(int i = head[u]; i != -1; i = edge[i].nxt){int j = edge[i].to;if(j == f) continue;dfs1(d + 1, u, j);size[u] += size[j];	//size记录子树节点总数 if(size[son[u]] < size[j])//找出重儿子 son[u] = j;}
}
void dfs2(int u, int tp)//u:当前节点，tp:链的顶端节点 
{top[u] = tp;id[u] = ++tot;num[tot] = u;if(son[u]) dfs2(son[u], tp);//重儿子优先 for(int i = head[u]; i != -1; i = edge[i].nxt){int j = edge[i].to;if(j == fa[u] || j == son[u]) continue;dfs2(j, j); }
}
void pushup(int m)
{tr[m].sum = tr[m<<1].sum + tr[m<<1|1].sum;
}
void build(int m, int l, int r)
{tr[m].l = l;tr[m].r = r;if(l == r){tr[m].sum = value[num[l]];return ;}int mid = (l + r) >> 1;build(m<<1, l, mid);build(m<<1|1, mid + 1, r);pushup(m);
}
void updata(int m, int id, int val)
{if(tr[m].l == id && tr[m].r == id){tr[m].sum = val;return ;}int mid = (tr[m].l + tr[m].r) >> 1;if(id <= mid) updata(m<<1, id, val);else updata(m<<1|1, id, val);pushup(m);
}
int ask(int m, int l, int r)
{if(tr[m].l >= l && tr[m].r <= r) return tr[m].sum;int res = 0;int mid = (tr[m].l + tr[m].r) >> 1;if(l <= mid) res += ask(m<<1, l, r);if(r > mid) res += ask(m<<1|1, l, r);return res;
}
int find(int s, int e)
{int fs = top[s];int fe = top[e];int tmp = 0;while(fs != fe){if(dep[fs] < dep[fe]){swap(fs, fe);swap(s, e);}tmp += ask(1, id[fs], id[s]);s = fa[fs];fs = top[s];}if(s == e) return tmp;if(dep[s] > dep[e]) swap(s, e);tmp += ask(1, id[son[s]], id[e]);return tmp;
}
int main()
{cnt = tot = 0;memset(head, -1, sizeof head);memset(size, 0, sizeof size);scanf("%d %d %d", &n, &q, &s);for(int i = 1; i < n; i++){path[i].read();add(path[i].x, path[i].y);add(path[i].y, path[i].x);}dfs1(1, 0, 1);dfs2(1, 1);value[1] = 0;for(int i = 1; i < n; i++)//将每条边的权值赋给深度大的端点 {if(dep[path[i].x] < dep[path[i].y])swap(path[i].x, path[i].y);value[path[i].x] = path[i].val;}build(1, 1, n);while(q--){int op, u, val;scanf("%d", &op);if(op == 0){scanf("%d", &u);printf("%d\n", find(s, u));s = u;}else{scanf("%d %d", &u, &val);updata(1, id[path[u].x], val);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！