LightOJ 1348(Aladdin and the Return Journey )
2024-10-19 00:25:27
题目链接:传送门
题目大意:一棵无根树,每个点上有权值,两种操作,0 x y询问x~y路径上权值和 1 x y将
节点 x 权值变为y。对于询问操作输出答案。
题目思路:树链剖分
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 30005
#define maxn 30010
typedef pair<int,int> PII;
typedef long long LL;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,k,v,head[N],a[N],hcnt,L,R;
struct Edge{int to,nxt;}node[N<<];
int son[N],siz[N],id[N],tid;
int fa[N],top[N],dep[N],posi[N];
LL seg[N<<];
void init(){
mst(head,-);mst(id,);mst(siz,);
mst(son,);hcnt=tid=;
}
void dfs1(int u,int f,int deep){
fa[u]=f,dep[u]=deep,siz[u]=;
for(int i=head[u];~i;i=node[i].nxt){
int e=node[i].to;if(e==f)continue;
dfs1(e,u,deep+);siz[u]+=siz[e];
if(!son[u]||siz[son[u]]<siz[e])son[u]=e;
}
}
void dfs2(int u,int tp){
top[u]=tp,id[u]=++tid,posi[tid]=u;
if(!son[u])return;dfs2(son[u],tp);
for(int i=head[u];~i;i=node[i].nxt){
int e=node[i].to;
if(!id[e])dfs2(e,e);
}
}
void build(int rt,int l,int r){
if(l==r){seg[rt]=a[posi[l]];return;}
int mid=l+r>>;
build(lson);build(rson);
seg[rt]=seg[rt<<]+seg[rt<<|];
}
void update(int rt,int l,int r){
if(l==r){seg[rt]=v;return;}
int mid=l+r>>;
if(L<=mid)update(lson);
else update(rson);
seg[rt]=seg[rt<<]+seg[rt<<|];
}
LL query(int rt,int l,int r){
if(L<=l&&r<=R)return seg[rt];
int mid=l+r>>;LL temp=;
if(L<=mid)temp+=query(lson);
if(R>mid) temp+=query(rson);
return temp;
}
void lca(int x,int y){
LL res=;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
L=id[top[x]],R=id[x];
res+=query(,,n);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
L=id[y],R=id[x];
res+=query(,,n);
printf("%lld\n",res);
}
int main(){
int i,j,group,x,y,Case=;
group=read();
while(group--){
init();
n=read();
for(i=;i<=n;++i)a[i]=read();
for(i=;i<n;++i){
x=read(),y=read();
++x;++y;
node[hcnt].to=y,node[hcnt].nxt=head[x],head[x]=hcnt++;
node[hcnt].to=x,node[hcnt].nxt=head[y],head[y]=hcnt++;
}
dfs1(,,);dfs2(,);build(,,n);
m=read();
printf("Case %d:\n",++Case);
while(m--){
x=read();
if(!x){
x=read(),y=read();
++x;++y;
lca(x,y);
}
else{
x=read(),y=read();
++x;
L=id[x],v=y;
update(,,n);
}
}
}
return ;
}
最新文章
- 罗马数字转整数Leetcode13
- (转)Redis使用场景及使用经验
- json中含有Unicode的处理办法 C#
- class.c 添加中文注释(1)
- JAVASE02-Unit07: 基本IO操作 、 文本数据IO操作
- php用正则检测某字段开头是否为字母
- 记一次Redis和NetMQ的测试
- webstorage[html5的本地数据处理]
- JavaScript设计模式——前奏
- 1-MSP430点亮一个灯
- POJ3321 Apple Tree(DFS序)
- iscroll4框架解析[webapp开发](转)
- ORA-1653: unable to extend table SYS.AUD$
- 使用自定义脚本扩展程序自动执行 VM 自定义任务
- POJ	2062 HDU 1528 ZOJ 2223 Card Game Cheater
- gridcontrol第一行为0,没有选中为-999999
- 深入Android RxJava 2
- Studio 一些使用
- OpenCV——PS滤镜,渐变映射
- ES6 的面向对象