本文主要是介绍codeforces COMPFEST-13 I. Illusions of the Desert 树剖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
I. Illusions of the Desert
(rating: 2300)
链接
https://codeforces.com/contest/1575/problem/I
题意
给一棵n个节点的树，点权为ai 。
要求对链做区间查询，单点修改。查的是边权和，边权的定义为： wab = max(|ax+ay|,|ax−ay|)。
input
6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3
output
39
32
0
思路
观察发现： max(|ax+ay|,|ax−ay|) = |ax| + |ay| , 然后就是树链剖分的事儿了。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
struct E{int to;int nxt;
}e[N<<1];
int head[N],tot;
void add_edge(int u,int v){e[++tot].to = v;e[tot].nxt = head[u];head[u] = tot;
}
int a[N];
int n,q;
int mson[N],siz[N],fa[N],deep[N];
void dfs1(int u,int f){int MAX_SON = 0;fa[u] = f;siz[u] = 1;deep[u] = deep[f]+1;for(int i=head[u];i;i=e[i].nxt){int v = e[i].to;if(v==f) continue;dfs1(v,u);siz[u] += siz[v];if(siz[v]>MAX_SON){MAX_SON = siz[v];mson[u] = v;}}
}
int dfn[N],idx,top[N],w[N],tr[N<<2];
void dfs2(int u,int t){dfn[u] = ++idx;top[u] = t;w[idx] = a[u];if(!mson[u]) return;dfs2(mson[u],t);for(int i=head[u];i;i=e[i].nxt){int v = e[i].to;if(v==fa[u]||v==mson[u]) continue;dfs2(v,v);}
}
void build(int now,int l,int r){if(l==r){tr[now] = w[l];return;}int mid = (l+r)>>1;build(now*2,l,mid);build(now*2+1,mid+1,r);tr[now] = tr[now*2]+tr[now*2+1];
}
void update(int now,int l,int r,int loc,int x){if(l==r){tr[now] = x;return;}int mid = (l+r)>>1;if(loc<=mid)update(now*2,l,mid,loc,x);elseupdate(now*2+1,mid+1,r,loc,x);tr[now] = tr[now*2]+tr[now*2+1];
}
int query(int now,int l,int r,int ql,int qr){int sum = 0;if(l>=ql&&r<=qr){sum += tr[now];return sum;}int mid = (l+r)>>1;if(ql<=mid)sum += query(now*2,l,mid,ql,qr);if(qr>mid)sum += query(now*2+1,mid+1,r,ql,qr);return sum;
}
int qchain(int x,int y){int ans = 0;while (top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);ans += query(1,1,n,dfn[top[x]],dfn[x]);x = fa[top[x]];}if(deep[x]>deep[y]){swap(x,y);}ans += query(1,1,n,dfn[x],dfn[y]);return ans;
}
signed main(){ios::sync_with_stdio(false);cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]<0) a[i] = -a[i];}for(int i=1;i<n;i++){int x,y;cin>>x>>y;add_edge(x,y);add_edge(y,x);}dfs1(1,0);dfs2(1,0);build(1,1,n);while(q--){int opt;cin>>opt;if(opt==1){int x,y;cin>>x>>y;x = dfn[x];update(1,1,n,x,abs(y));}else{int x,y;cin>>x>>y;cout<<2* qchain(x,y)- qchain(x,x)- qchain(y,y)<<endl;}}return 0;
}
这篇关于codeforces COMPFEST-13 I. Illusions of the Desert 树剖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
