T247910题解

第一步：分析题目#

清空一段管道的费用为从根节点出发道某段管道所用费用的积.

请输出清空所有管道所需费用;

Example

可以看出，对于每一棵子树，其子节点的数据均与其根节点的数据有关，因此很容易想到把每一个节点的数据都进行记录，并进行前序遍历。故有：

struct node{
    int F,L,R,C,len=1;  //F父节点，L左孩子，R右孩子，C所用花费，len答案长度（默认为1）
    long long res[250]={1};  //res每一段结果数组(第一位必为1，否则0乘以任何数等于0)
}a[110]; //节点个数

cpp

并通过如下代码输入：

 cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>ro>>f1>>s1>>f2>>s2;  //ro,f1,s1,f2,s2分别为当前节点，左孩子，到左孩子所用值，右孩子，到右孩子所用值
        if(f1) a[ro].L=f1,a[f1].F=ro,a[f1].C=s1;
        if(f2) a[ro].R=f2,a[f2].F=ro,a[f2].C=s2;
    }

cpp

为进行前序遍历,先找到根：

queue <int> Q;
for(int i = 1;i<=n;i++){
    if(a[i].F==0){  //若此节点无父亲，则为根节点
        root=i;
        break;
    }
}

cpp

第二步：分析数据范围#

对于 100% 的数据，保证1<=n<=110,所有输入数据不大于LLONG_MAX

对于30%的数据，保证答案在long long 以内

对于70%的数据，无限制

显而易见，本题应使用高精；

由于输入数据不大于 LLONG_MAX，故本题为高精乘低精，高精加高精；

为进行高精乘低精，故有：

void cheng(int x,int who,int child){  //x乘数，who父亲，child孩子
    int p=0;  //进位
    a[child].len=a[who].len;
	for(int i=0;i<a[child].len;i++){
	    a[child].res[i]=a[who].res[i]*x+p;  //对每一位进行处理
            p=a[child].res[i]/10;  //更新进位
	    a[child].res[i]%=10;  //更新当前位
	}
	while(p){  //处理总位数
	    a[child].res[a[child].len]=p;
	    p/=10;
	    a[child].res[a[child].len++]%=10;  //更新位数len
	}
}

cpp

为进行高精加高精，故有：

long long RES[1000]; //最终答案
int LEN=1; //最终答案位数
void add(int who){ //当前节点
	int l=max(LEN,a[who].len),p=0;  //l取最大位数进行加法运算，p进位
	LEN=l;
	for(int i=0;i<l;i++){
		RES[i]=RES[i]+a[who].res[i]+p;
		p=RES[i]/10;
		RES[i]%=10;
	}
	if(p) RES[LEN++]=p;  //更新最终位数
}

cpp

第三步：树的遍历#

本题可以用递归，也可以用队列，这里给出队列的做法：

Q.push(root);  //把一开始找到的根加入队列
while(!Q.empty()){
    int now=Q.front();
    Q.pop();
    if(a[now].L){  //如果有左儿子
        Q.push(a[now].L);
        cheng(a[a[now].L].C,now,a[now].L);  //高精乘法
        add(a[now].L);  //高精加
    }
    if(a[now].R){  //如果有右儿子
        Q.push(a[now].R);
        cheng(a[a[now].R].C,now,a[now].R);  //高精乘法
        add(a[now].R);  ////高精加
    }
}

cpp

最后输出答案：

for(int i = LEN-1;i>=0;i--){
    cout<<RES[i];
}

cpp

#

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct node{
    int F,L,R,C,len=1;
    long long res[250]={1};
}a[110];
queue <int> Q;
long long RES[1000];
int len=1;
void cheng(int x,int who,int child){
    int p=0;
    a[child].len=a[who].len;
    for(int i=0;i<a[child].len;i++){
            a[child].res[i]=a[who].res[i]*x+p;
            p=a[child].res[i]/10;
            a[child].res[i]%=10;
    }
    while(p){
            a[child].res[a[child].len]=p;
            p/=10;
            a[child].res[a[child].len++]%=10;
    }
}
void add(int who){
    int l=max(len,a[who].len),p=0;
    len=l;
    for(int i=0;i<l;i++){
            RES[i]=RES[i]+a[who].res[i]+p;
            p=RES[i]/10;
            RES[i]%=10;
    }
    if(p) RES[len++]=p;
}
int main(){
    int n,ro,f1,s1,f2,s2,root;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>ro>>f1>>s1>>f2>>s2;
        if(f1) a[ro].L=f1,a[f1].F=ro,a[f1].C=s1;
        if(f2) a[ro].R=f2,a[f2].F=ro,a[f2].C=s2;
    }
    for(int i = 1;i<=n;i++){
        if(a[i].F==0){
            root=i;
            break;
        }
    }
    Q.push(root);
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        if(a[now].L){
            Q.push(a[now].L);
            cheng(a[a[now].L].C,now,a[now].L);
            add(a[now].L);
        }
        if(a[now].R){
            Q.push(a[now].R);
            cheng(a[a[now].R].C,now,a[now].R);
            add(a[now].R);
        }
    }
    for(int i = len-1;i>=0;i--){
        cout<<RES[i];
    }
}

cpp

第一步：分析题目#

第二步：分析数据范围#

第三步：树的遍历#

#

Comments