题意: 知道了一颗有  n 个节点的树和树上每条边的权值,对应两种操作:

0 x        输出 当前节点到 x节点的最短距离,并移动到 x 节点位置

1 x val   把第 x 条边的权值改为 val

题意: 知道了一颗有  n 个节点的树和树上每条边的权值,对应两种操作:

0 x        输出 当前节点到 x节点的最短距离,并移动到 x 节点位置

1 x val   把第 x 条边的权值改为 val

LCA +RMQ+树状数组

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = 2e5+; int N,Q,S;
//vector <int> G[maxn]; struct edge{
int to,next,w;
}e[*maxn]; int head[*maxn],tot;
void add_edge(int u,int v,int w)
{
e[tot].to = v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot++; e[tot].to = u;
e[tot].w = w;
e[tot].next = head[v];
head[v] = tot++;
} int in[maxn],out[maxn],P[*maxn],fa[maxn][],dep[maxn],dis[maxn],cnt;
void dfs(int u,int _fa,int _dep,int _dis)
{
in[u] = ++cnt;
P[cnt] = u;
fa[u][] = _fa;
dis[u] = _dis;
dep[u] = _dep;
for(int i=head[u];~i;i=e[i].next)
{
int v = e[i].to;
if(v == _fa) continue;
dfs(v,u,_dep+,_dis+e[i].w);
}
out[u] = ++cnt;
}
void debug()
{
printf("in:\t");for(int i=;i<=N;i++) printf("%d ",in[i]);puts("");
printf("out:\t");for(int i=;i<=N;i++) printf("%d ",out[i]);puts("");
printf("p:\t");for(int i=;i<=cnt;i++) printf("%d ",P[i]);puts("");
printf("dis:\t");for(int i=;i<=N;i++) printf("%d ",dis[i]);puts("");
printf("dep:\t");for(int i=;i<=N;i++) printf("%d ",dep[i]);puts("");
printf("edge:");for(int i=;i<tot;i++) printf("\tto:%d w:%d\n",e[i].to,e[i].w);
} int initLCA()
{
int m = (int)log(N)/log()+;
for(int k=;k<m;k++)
{
for(int v=;v<=N;v++)
{
if(fa[v][k] < ) {fa[v][k+] = -;continue;}
else fa[v][k+] = fa[fa[v][k]][k];
}
}
} int LCA(int u,int v)
{
int m = (int)log(N)/log()+;
if(dep[v] > dep[u]) swap(u,v);
for(int k=;k<m;k++)
{
if((dep[u]-dep[v])>>k & )
u = fa[u][k];
}
if(u == v) return u;
for(int k=m-;k>=;k--)
{
if(fa[u][k] != fa[v][k])
{
u = fa[u][k];
v = fa[v][k];
}
}
return fa[u][];
} int c[*maxn];
int lowbit(int x) {return x&-x;} void init()
{
memset(head,-,sizeof head);
memset(fa,-,sizeof fa);
memset(c,,sizeof c);
memset(in,,sizeof in);
memset(out,,sizeof out);
tot = ;
cnt = ;
} void add(int x,int d)
{
while(x)
{
c[x] += d;
x -= lowbit(x);
}
}
void add_seg(int l,int r,int d)
{
add(r,d);
add(l-,-d);
}
int sum(int x)
{
int res = ;
//printf("u:%d ",P[x]);
while(x <= cnt)
{
res += c[x];
x += lowbit(x);
}
//printf("res:%d\n",res);
return res;
}
int dist(int x)
{
if(x == -) return ;
return sum(in[x]) + dis[x];
}
int main()
{
//freopen("input.txt","r",stdin);
while(~scanf("%d%d%d",&N,&Q,&S))
{
init();
for(int i=,u,v,w;i<N-;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
dfs(,-,,);
//debug();
initLCA();
for(int i=;i<tot;i+=)
{
if(dep[e[i].to] < dep[e[i+].to]) swap(e[i].to,e[i+].to);
}
int op;
for(int i=,a,b,c;i<Q;i++)
{
scanf("%d",&op);
if(op == )
{
scanf("%d",&a);
int lca = LCA(S,a);
//printf("lca:%d\n",lca); printf("%d\n",dist(S)+dist(a)-*(dist(lca)));
S = a;
}else
{
scanf("%d%d",&a,&b);
a--;
int u = e[a*].to;
int dw = b - (dist(u) - dist(fa[u][]));
//printf("dw:%d u:%d\n",dw,u);
add_seg(in[u],out[u],dw);
}
}
}
}

树链部分

#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + ;
int n, q, s;
int fa[MAXN]; // fa[v]: v 的父亲
int dep[MAXN]; // dep[v]: v 的深度(根深度为1)
int siz[MAXN]; // : 以 v 为根的子树的节点数
int son[MAXN]; // : 重儿子,siz[u] 为 v 的子节点中 siz 值最大的,那么 u 就是 v 的重儿子
int top[MAXN]; // : 表示 v 所在的重链的顶端节点
int w[MAXN]; // : 表示 v 与其父亲节点的连边在线段树中的位置
int num; // 将树映射到线段树上的标号
int cnt, head[MAXN];
struct Edge {
int to, next;
}edge[MAXN];
struct E {
int u, v, c;
}e[MAXN];
void addedge(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int u) {
siz[u] = ; son[u] = ;
for(int i = head[u]; ~i; i = edge[i].next) {
if(edge[i].to != fa[u]) {
fa[edge[i].to] = u;
dep[edge[i].to] = dep[u] + ;
dfs(edge[i].to);
if(siz[edge[i].to] > siz[son[u]]) son[u] = edge[i].to;
siz[u] += siz[edge[i].to];
}
}
}
void build_tree(int u, int tp) {
w[u] = ++num; top[u] = tp;
if(son[u]) build_tree(son[u], top[u]); // 使重链各边在线段树中呈连续分布
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v != son[u] && v != fa[u])
build_tree(v, v);
}
}
ll sum[MAXN];
void pushUp(int rt) {
sum[rt] = sum[rt << ] + sum[rt << | ];
}
void build(int l, int r, int rt) {
sum[rt] = ;
if(l == r) return;
int m = (l + r) / ;
build(lson); build(rson);
}
void update(int p, int c, int l, int r, int rt) {
if(l == r) {
sum[rt] = c;
return;
}
int m = (l + r) / ;
if(m >= p) update(p, c, lson);
else update(p, c, rson);
pushUp(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r) return sum[rt];
int m = (l + r) / ;
ll res = ;
if(m >= L) res += query(L, R, lson);
if(m < R) res += query(L, R, rson);
return res;
}
void change(int v, int c) {
if(dep[e[v].u] > dep[e[v].v]) update(w[e[v].u], c, , n, );
else update(w[e[v].v], c, , n, );
}
ll seek(int v, int u) {
int t1 = top[v], t2 = top[u];
ll res = ;
while(t1 != t2) {
if(dep[t1] < dep[t2]) {
swap(t1, t2); swap(v, u);
}
res += query(w[t1], w[v], , n, );
v = fa[t1]; t1 = top[v];
}
if(v == u) return res;
if(dep[v] > dep[u]) swap(v, u);
return res + query(w[son[v]], w[u], , n, );
}
int main() {
memset(head, -, sizeof head);
cnt = num = ;
scanf("%d%d%d", &n, &q, &s);
for(int i = ; i < n; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
addedge(e[i].u, e[i].v);
addedge(e[i].v, e[i].u);
}
dfs();
build_tree(, );
build(, n, );
for(int i = ; i < n; i++) {
if(dep[e[i].u] > dep[e[i].v]) update(w[e[i].u], e[i].c, , n, );
else update(w[e[i].v], e[i].c, , n, );
}
while(q--) {
int cc;
int x, y;
scanf("%d", &cc);
if(cc) {
scanf("%d%d", &x, &y);
change(x, y);
} else {
scanf("%d", &x);
printf("%lld\n", seek(s, x));
s = x;
}
}
return ;
}

最新文章

  1. Android中的沉浸式状态栏效果
  2. [Q&amp;A] C1DataGrid 奇葩的 BeginNewRow() 方法
  3. linux split 及优化
  4. 用Java语言编写一个简易画板
  5. Amr and Chemistry CodeForces 558C(BFS)
  6. [转]C# List&lt;T&gt;的详细用法
  7. java实现 swing模仿金山打字 案例源码
  8. 特殊的反转单链表算法(C++)
  9. POJ_1182_食物链_[NOI]_(并查集)
  10. PHP android ios相互兼容的AES加密算法
  11. Pod install Error List
  12. yum搭建 Lamp环境
  13. Ubuntu16.04 + gtx1060 + cuda8.0 + cudnn5.1 + caffe + Theano + Tensorflow
  14. vue.js的项目实战
  15. JWT 从入门到精通
  16. 测试dos攻击对openflow中flow_table溢出的影响
  17. 02:BeautifulSoup
  18. static 和 global
  19. Task 6.4 冲刺Two之站立会议4
  20. 浏览器根对象window之history

热门文章

  1. Ubuntu无法安装rpm包,ubuntu RPM should not be used directly install RPM packages, use Alien instead!
  2. Ubuntu 查看软件版本
  3. Hyperledger Fabric开发
  4. IP命令的用法详解
  5. MagicNotes:突破来自外界的脑力压制
  6. PHP文件的引用
  7. [GO]随机生成四们数字
  8. datetime 2017-10-21 10:09:02.560 转年月日的时间类型
  9. python学习手册 (第3版)
  10. jquery操作select(取值,设置选中) 基础