首页 > 代码库 > POJ 2763 (树链剖分+边修改+边查询）
POJ 2763 (树链剖分+边修改+边查询）
题目链接：http://poj.org/problem?id=2763
题目大意：某人初始在s点。有q次移动，每次移动沿着树上一条链，每经过一条边有一定花费，这个花费可以任意修改。问每次移动的花费。
解题思路：
树链剖分基础题。每次Q之后改变一下s。
线段树记录的是边权。方法是对于一条边（u,v)，边权值加在dep比较大的那一端。
链查询（边）和 链查询（点）在轻链时略有不同。
注意本题使用vector邻接表存图是会TLE的，应该使用链式前向星。树链剖分中使用链式前向星是基本要求。
#include "cstdio"#include "cstring"using namespace std;#define maxn 100005int s[maxn],dep[maxn],w[maxn],fa[maxn],top[maxn],son[maxn],val[maxn],cnt,tol,n;int head[maxn];struct Edge{ int u,v,c;}edge[maxn];struct EDGE{ int next,to;}e[2*maxn];void addedge(int u,int v){ e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}void dfs1(int u,int pre,int d){ s[u]=1;fa[u]=pre;dep[u]=d; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(v==pre) continue; dfs1(v,u,d+1); s[u]+=s[v]; if(son[u]!=-1||s[v]>s[son[u]]) son[u]=v; }}void dfs2(int u,int tp){ w[u]=++cnt;top[u]=tp; if(son[u]==-1) return; dfs2(son[u],tp); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); }}//Segment Tree#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1int sum[maxn<<2];void PushUp(int root){ sum[root]=sum[root<<1]+sum[root<<1|1];}void Build(int l,int r,int root){ if(l==r) { sum[root]=val[l]; return; } int mid=(l+r)>>1; Build(lson); Build(rson); PushUp(root);}void Update(int p,int v,int l,int r,int root){ if(l==r) { sum[root]=v; return; } int mid=(l+r)>>1; if(p<=mid) Update(p,v,lson); else Update(p,v,rson); PushUp(root);}int Query(int L,int R,int l,int r,int root){ if(L<=l&&r<=R) return sum[root]; int mid=(l+r)>>1; int ret=0; if(L<=mid) ret+=Query(L,R,lson); if(R>mid) ret+=Query(L,R,rson); return ret;}void Change(int x,int v){ if(dep[edge[x].u]>dep[edge[x].v]) Update(w[edge[x].u],v,1,n,1); else Update(w[edge[x].v],v,1,n,1);}int query(int x,int y){ int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=Query(w[top[x]],w[x],1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); if(x!=y) ans+=Query(w[son[x]],w[y],1,n,1);// return ans;}int main(){ //freopen("in.txt","r",stdin); int m,s,u,t,cmd; while(~scanf("%d%d%d",&n,&m,&s)) { memset(son,-1,sizeof(son)); memset(head,-1,sizeof(head)); cnt=tol=0; for(int i=1;i<n;i++) { scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].c); addedge(edge[i].u,edge[i].v); addedge(edge[i].v,edge[i].u); } dfs1(1,1,1); dfs2(1,1); for(int i=1;i<n;i++) { if(dep[edge[i].u]>dep[edge[i].v]) val[w[edge[i].u]]=edge[i].c; else val[w[edge[i].v]]=edge[i].c; } Build(1,n,1); while(m--) { scanf("%d",&cmd); if(cmd==0) { scanf("%d",&t); printf("%d\n",query(s,t)); s=t; } if(cmd==1) { scanf("%d%d",&u,&t); Change(u,t); } } }}
| 13493821 | neopenx | 2763 | Accepted | 9676K | 1579MS | C++ | 3176B | 2014-10-01 16:16:22 |
POJ 2763 (树链剖分+边修改+边查询）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。