[原创]POJ 2763 Housewife Wind [树链剖分(边权)+树状数组]【数据结构】

2017-03-09 22:59:37 Tabris_ 阅读数：279

博客爬取于2020-06-14 22:41:24
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/60982742

题目连接：http://poj.org/problem?id=2763
--------------------------------------------------------------------------.
Housewife Wind
Time Limit: 4000MS Memory Limit: 65536K
Total Submissions: 10703 Accepted: 2969
Description

After their royal wedding, Jiajia and Wind hid away in XX Village, to enjoy their ordinary happy life. People in XX Village lived in beautiful huts. There are some pairs of huts connected by bidirectional roads. We say that huts in the same pair directly connected. XX Village is so special that we can reach any other huts starting from an arbitrary hut. If each road cannot be walked along twice, then the route between every pair is unique.

Since Jiajia earned enough money, Wind became a housewife. Their children loved to go to other kids, then make a simple call to Wind: ‘Mummy, take me home!’

At different times, the time needed to walk along a road may be different. For example, Wind takes 5 minutes on a road normally, but may take 10 minutes if there is a lovely little dog to play with, or take 3 minutes if there is some unknown strange smell surrounding the road.

Wind loves her children, so she would like to tell her children the exact time she will spend on the roads. Can you help her?
Input

The first line contains three integers n, q, s. There are n huts in XX Village, q messages to process, and Wind is currently in hut s. n < 100001 , q < 100001.

The following n-1 lines each contains three integers a, b and w. That means there is a road directly connecting hut a and b, time required is w. 1<=w<= 10000.

The following q lines each is one of the following two types:

Message A: 0 u
A kid in hut u calls Wind. She should go to hut u from her current position.
Message B: 1 i w
The time required for i-th road is changed to w. Note that the time change will not happen when Wind is on her way. The changed can only happen when Wind is staying somewhere, waiting to take the next kid.
Output

For each message A, print an integer X, the time required to take the next child.
Sample Input

3 3 1
1 2 1
2 3 2
0 2
1 2 3
0 3
Sample Output

1
3
--------------------------------------------------------------------------.
题目大意：
一颗n个节点的生成树，有边权，一个人开始在s位置，有两种操作，
1） 0 a 从s走到n 输出路径长度
2） 1 a b 将第a条边的权值变成b

解题思路：
这题就是基于边权的树链剖分。找路径的和我们可以采用树状数组维护

其实边权对于点权来说，基本一样，我们只要将u->v的权值给u，v中距离根节点远的就行了
然后查找的时候再讲lca(u,v)这个点的权值减去 得到的就是u->v的路径长度

注意下本题卡时间卡的非常紧
vector是不行的 要用前向星 .

附本题代码
--------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
# include <stdio.h>
# include <vector>
using namespace std;

typedef long long int LL;

const int    INF = (~(1<<31));
const int    N   = 100000+7;
const double eps = 1e-7;

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/****************************************************/

int n,q,s;
int head[N],tot;
struct edge{
    int to,next;
}G[N*10];
int temp;

void myswap(int &a,int &b){
    temp=a;
    a=b;
    b=temp;
}

void add(int u,int v){
    G[tot].to=v;G[tot].next=head[u];head[u]=tot++;
    G[tot].to=u;G[tot].next=head[v];head[v]=tot++;
}

int dep[N],fa[N],sz[N],son[N];
int top[N],tree[N],cnt;

void dfs1(int u,int ff,int deep){
    son[u]=0;fa[u]=ff;sz[u]=1;dep[u]=deep;
    for(int i=head[u];i!=-1;i=G[i].next){
        int v=G[i].to;
        if(v==ff) continue;
        dfs1(v,u,deep+1);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int ff){
    tree[u]=++cnt;top[u]=ff;
    if(son[u]) dfs2(son[u],ff);
    else return ;
    for(int i=head[u];i!=-1;i=G[i].next){
        int v=G[i].to;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}

int sum[N];
# define lowbit(x) (x&-x)
void update(int i,int val){
    for(;i&&i<=n;i+=lowbit(i))
        sum[i]+=val;
}
int getSum(int i){
    int ans=0;
    for(;i;i-=lowbit(i))ans+=sum[i];
    return ans;
}

int findi(int x,int y){
    int fx=top[x],fy=top[y];
    int ans = 0;
    while(fx!=fy){
        if(dep[fx]<dep[fy]) myswap(x,y),myswap(fx,fy);
        ans+=getSum(tree[x])-getSum(tree[fx]-1);
        x=fa[fx],fx=top[x];
    }
    if(dep[x]>dep[y]) myswap(x,y);
    if(x!=y) ans+=getSum(tree[y])-getSum(tree[x]);
    return ans ;
}

void init(){
    for(int i=0;i<=n;i++) son[i]=0;
    cnt=tot=0;
    for(int i=0;i<=n;i++) head[i]=-1;
}


int u[N],v[N],w[N];


int main(){
    while(~scanf("%d%d%d",&n,&q,&s)){
        init();

        for(int i=1;i<n;i++){
            u[i]=read(),v[i]=read(), w[i]=read();
            add(u[i], v[i]);
        }

        dfs1(1,0,1);
        dfs2(1,1);
        for(int i=1;i<n;i++){
            if(fa[ u[i]]== v[i]) myswap( u[i], v[i]);
            update(tree[ v[i]], w[i]);
        }
        int op,id,ww,b;
        while(q--){
            op=read();
            if(op){
                id=read(),ww=read();
                update(tree[v[id]],ww-w[id]);
                w[id]=ww;
            }
            else {
                b=read();
                printf("%d\n",findi(s,b));
                s=b;
            }
        }
        for(int i=0;i<=n;i++) sum[i]=0;
    }
    return 0;
}