poj2763 Housewife Wind 树链剖分 - c++编程基础

TOP

poj2763 Housewife Wind 树链剖分

2015-07-20 17:24:10 来源: 作者: 【大中小】浏览:1次

题意：给定树的结点数n，初始起点s，有两个操作，(1) 0 u 查询从当前位置到u的时间，当前位置变为u (2) 1 i w 修改第i条路花的

时间为w。

思路：树链剖分。剖分完，线段树单点更新，区间查询。详见代码：

/*********************************************************
  file name: poj2763.cpp
  author : kereo
  create time:  2015年01月23日 星期五 08时28分06秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=100+50; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int n,m,st,edge_cnt,cnt; int head[MAXN],sz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],pos[MAXN],top[MAXN]; struct Edge{ int u,v,w,next; }edge[MAXN<<1]; struct node{ int l,r,sum; }segtree[MAXN<<2]; void init(){ edge_cnt=cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w){ edge[edge_cnt].u=u; edge[edge_cnt].v=v; edge[edge_cnt].w=w; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++; } void dfs1(int u,int pre,int depth){ sz[u]=1; fa[u]=pre; son[u]=0; dep[u]=depth; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == pre) continue; dfs1(v,u,depth+1); sz[u]+=sz[v]; if(sz[son[u]]
              
               >1; build(L(rt),l,mid); build(R(rt),mid+1,r); } void update(int rt,int p,int x){ if(segtree[rt].l == segtree[rt].r){ segtree[rt].sum=x; return ; } int mid=(segtree[rt].l+segtree[rt].r)>>1; if(p<=mid) update(L(rt),p,x); else update(R(rt),p,x); push_up(rt); } int query(int rt,int l,int r){ if(segtree[rt].l == l && segtree[rt].r == r) return segtree[rt].sum; int mid=(segtree[rt].l+segtree[rt].r)>>1; if(r<=mid) return query(L(rt),l,r); else if(l>mid) return query(R(rt),l,r); else return query(L(rt),l,mid)+query(R(rt),mid+1,r); } int solve(int u,int v){ int ans=0; while(top[u]!=top[v]){ if(dep[top[u]]
               
                dep[v]) swap(u,v); if(u!=v) ans+=query(1,pos[u]+1,pos[v]); return ans; } int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&n,&m,&st)){ init(); for(int i=1;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu5163---Taking Bus	下一篇：Follow me---快速入门shell脚本编..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: