程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj2763 Housewife Wind 樹鏈剖分

poj2763 Housewife Wind 樹鏈剖分

編輯：關於C++

題意：給定樹的結點數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