首页 > 代码库 > POJ 2763 Housewife Wind(树链剖分+树状数组)
POJ 2763 Housewife Wind(树链剖分+树状数组)
【题目链接】 http://poj.org/problem?id=2763
【题目大意】
在一棵树上,给出一些边的边长,有修改边的边长的操作,
询问每次从当前点到目标点的最短距离
【题解】
树链剖分之后,相当于树状数组的单点更新和区间查询,
注意边权转点权之后链操作不覆盖deep最浅的点,这里容易出错
【代码】
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=200010; int tot,x,d[N],num[N],ed=0,u,w,n,m,i,v[N],vis[N],f[N],g[N];int nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;char ch;void add_edge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void init(){ memset(g,dfn=ed=0,sizeof(g)); memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt)); memset(son,-1,sizeof(son));}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x,d[v[i]]=d[x]+1; dfs(v[i]),size[x]+=size[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; }}void dfs2(int x,int y){ if(x==-1)return; st[x]=++dfn;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]); en[x]=dfn;}int c[N];void add(int x,int val){while(x<=dfn)c[x]+=val,x+=x&-x;}int query(int x){int s=0;while(x)s+=c[x],x-=x&-x;return s;}int chain(int x,int y){ int res=0; for(;top[x]!=top[y];x=f[top[x]]){ if(d[top[x]]<d[top[y]]){int z=x;x=y;y=z;} res=res+query(st[x])-query(st[top[x]]-1); }if(d[x]<d[y]){int z=x;x=y;y=z;} //注意边权转为子节点点权时,链操作不操作deep最浅的点,左端点为开节点 res=res+query(st[x])-query(st[y]); return res; }int e[N][3],q,s;int main(){ while(~scanf("%d%d%d",&n,&q,&s)){ init(); memset(c,0,sizeof(c)); for(int i=1;i<n;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); add_edge(e[i][0],e[i][1]); add_edge(e[i][1],e[i][0]); }dfs(1);dfs2(1,1); for(int i=1;i<n;i++){ if(d[e[i][0]]>d[e[i][1]])swap(e[i][0],e[i][1]); add(st[e[i][1]],e[i][2]); }int op,x,y; while(q--){ scanf("%d",&op); if(op==0){ scanf("%d",&x); printf("%d\n",chain(x,s)); s=x; }else{ scanf("%d%d",&x,&y); add(st[e[x][1]],y-e[x][2]); e[x][2]=y; } } }return 0;}
POJ 2763 Housewife Wind(树链剖分+树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。