数据结构程序设计实践-收费

Question

问题遇到的现象和发生背景

算法与数据结构

★实验任务

有一张无限大的图，图中的节点编号从1开始。图中节点由无向边连接，编号为i的节点分别与2i号节点和2i+1号节点连接，显然任意两个点之间的最短路是确定的且唯一的。最开始每条边上的花费都是0。 接下来有两种操作

给从u到v的最短路上的每条边都加上w的花费

计算走最短路从u到v的总花费（即路上所有边的花费和）

★数据输入

第一行输入一个整数q，表示操作的数量，接下来q行，每行第一个数字代表操作的类型，如果是1号操作，则紧接着输入u，v，w三个整数；如果是2号操作，接着输入u，v两个整数。

★数据输出

对于每一个2号操作，输出一行一个数字，代表路上的总花费

输入示例
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
输出示例
94
0
32
★数据范围

50% : q <= 10, 1≤u,v,w≤1000

100% : q <= 1000, 1≤u,v≤1000000,w <= 1e9

我的解答思路和尝试过的方法

毫无思路，没有学习图的话，如何通过树来完成呢？

Answer 1

傻子做法：

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int treee[N];
int sum=0,flag=0;

int find_public_father(int u,int v){
    int t1=1,t2=1,arr1[10000],arr2[10000];
    arr1[0]=u; arr2[0]=v;
    while(u>1){
        u/=2;
        arr1[t1++]=u;
    }
    while(v>1){
        v/=2;
        arr2[t2++]=v;
    }
    for(int i=0;i<t1;i++){
        for(int j=0;j<t2;j++){
            if(arr1[i]==arr2[j]){
                return arr1[i];
            }
        }
    }
}

void add(int u,int v,int w){
    if(u==v){
        flag=1;
        return;
    }else if(u>v){
        return;
    }
    add(2*u,v,w);
    if(flag){
        treee[2*u]+=w;
        return;
    }
    add(2*u+1,v,w);
    if(flag){
        treee[2*u+1]+=w;
        return;
    }
}

void travel(int u,int v){
    if(u==v){
        flag=1;
        return;
    }else if(u>v){
        return;
    }
    travel(2*u,v);
    if(flag){
        sum+=treee[2*u];
        return;
    }
    travel(2*u+1,v);
    if(flag){
        sum+=treee[2*u+1];
        return;
    }
}

int main(){
    int q; cin >> q;
    while(q--){
        int x,u,v,w;; cin >> x;
        if(x==1){
            cin >> u >> v >> w;
            int father=find_public_father(u,v); 
            // cout << "their father is:" << father << endl;
            flag=0; add(father,u,w);
            flag=0; add(father,v,w);
        }else if(x==2){
            cin >> u >> v;
            int father=find_public_father(u,v);
            sum=0;
            flag=0; travel(father,u);
            flag=0; travel(father,v);
            cout << sum << endl;
        }
        // for(int i=0;i<8;i++){
        //     cout << treee[i] << " ";
        // }
    }
    // system("pause");
    return 0;
}

正解：https://www.cnblogs.com/wzl19981116/p/10087302.html

void Add(ll x,ll y,ll w)
{
    while(1)
    {
        if(x>y)
        {
            a[x]+=w;
            x/=2;
        }else if(x<y)
        {
            a[y]+=w;
            y/=2;
        }else
            break;
    }
}
ll query(ll x,ll y)
{
    ll ans=0;
    while(1)
    {
        if(x>y)
        {
            ans+=a[x];
            x/=2;
        }else if(x<y)
        {
            ans+=a[y];
            y/=2;
        }else
        {
            return ans;
        }
    }
}