首页 > 代码库 > light1348Aladdin and the Return Journey树链剖分
light1348Aladdin and the Return Journey树链剖分
点更新模版题,线段树 建树的时候没写更新,交了几十次吧。
#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1typedef long long LL;const int maxn = 333333;int son[maxn], size[maxn], head[maxn], deep[maxn], pos[maxn], vis[maxn], top[maxn];int father[maxn];int val[maxn];int sum[maxn << 2];struct Node{ int next; int to;}e[maxn * 2];int len, z;void init(int x){ size[x] = 1;son[x] = 0; for(int i=head[x];i!=-1;i=e[i].next){ int cc=e[i].to; if(cc==father[x]) continue; deep[cc] = deep[x]+1; father[cc] = x; init(cc); size[x]+=size[cc]; if(size[son[x]]<size[cc]) son[x] = cc; }}void dfs(int x, int tp){ pos[x] = ++z; vis[z] = x; top[x] = tp; if (son[x]) dfs(son[x], tp); for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x] || cc == son[x]) continue; dfs(cc,cc); }}void add(int from, int to){ e[len].to = to; e[len].next = head[from]; head[from] = len++;}void up(int rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void build(int l, int r, int rt){ if (l == r){ // printf("%d %d\n",l,val[vis[l]]); sum[rt] = val[vis[l]]; return; } int mid = (l + r) >> 1; build(lson); build(rson); up(rt);}void update(int key, int ans, int l, int r, int rt){ if (l == r){ sum[rt] = ans; return; } int mid = (l + r) >> 1; if (key <= mid) update(key, ans, lson); else update(key, ans, rson); up(rt);}int ask(int L, int R, int l, int r, int rt){ if (L <= l&&r <= R) return sum[rt]; int mid = (l + r) >> 1; int ans = 0; if (L <= mid) ans += ask(L, R, lson); if (R > mid) ans += ask(L, R, rson); return ans;}int gao(int x, int y){ int ans = 0; int fx = top[x]; int fy = top[y]; while (fx != fy){ if (deep[fx] < deep[fy]){ swap(x, y); swap(fx, fy); } ans += ask(pos[fx], pos[x], 1, z, 1); x = father[fx]; fx = top[x]; } if (deep[x]>deep[y]) swap(x, y); ans += ask(pos[x], pos[y], 1, z, 1); return ans;}int main(){ int t; int n; int a, b, c; int Icase = 0; scanf("%d",&t); int q; while (t--){ scanf("%d",&n); len = 0; z = 0; memset(head, -1, sizeof(head)); for (int i = 1; i <= n; i++){ scanf("%d", &val[i]); } for (int i = 1; i < n; i++){ scanf("%d%d", &a, &b); add(a + 1, b + 1); add(b + 1, a + 1); } init(1);dfs(1,1);build(1,z,1); scanf("%d",&q); printf("Case %d:\n", ++Icase); while (q--){ scanf("%d%d%d", &a, &b, &c); if (a == 0){ printf("%d\n",gao(b+1,c+1)); } else{ update(pos[b + 1], c, 1, z, 1); } } } return 0;}
light1348Aladdin and the Return Journey树链剖分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。