链接：https://ac.nowcoder.com/acm/contest/9984/H
来源：牛客网
题目描述
众所周知，吴楚月在数据结构课的大作业环节选择了表达式求值。
他觉得实现一个线性的表达式求值太无聊了，于是他把问题丢到了一棵树上。
形式化地讲，这棵树有 n 个节点，1 号点为根，每个节点上都有一个权值 vivi ，代表参与运算的值。每条边都有一个 opiopi ，代表运算符。
于是树上一条路径变成了 v−op−v−⋯−v−op−vv−op−v−⋯−v−op−v 的形式，对应一个表达式。
吴楚月希望你对树上每一个节点 u ，计算出根到 u 的简单路径所对应的表达式的值。
由于计算结果可能很大，所以你需要对 1e9+7 取模 。
注：表达式优先级即正常的加减乘除的优先级，从左往右，乘除优先级高于加减。
输入描述:
第一行给出一个整数 n 表示节点个数。
第二行 n 个正整数，第 i 个数表示 i 号节点的权值 vivi 。
第三行 n-1 个正整数，第 i 个数 faifai 表示 i+1 号节点的父亲。
第四行一个长度为 n-1 的字符串， 第 i 个字符表示 i+1 号节点与它父亲之间连边对应的运算符。
其中 1≤n≤1e51≤n≤1e5，1≤vi≤1e91≤vi≤1e9，1≤fai≤i1≤fai≤i，opi∈{+,−,∗,/}opi∈{+,−,∗,/}。
输出描述:
一行输出 n 个数字，其中第 i 个数字表示根到 i 号节点的路径所对应的表达式的值。
示例1
输入
复制
3
3 4 2
1 1
/*
输出
复制
3 750000006 6
比赛的时候看过的人不多以为要用到逆波兰表达式求值之类的来着，结束后突然发现并没有括号之类的东西Q^Q
爬了
题解写的挺好：
作者：九峰
链接：https://ac.nowcoder.com/discuss/596871?type=101&order=0&pos=1&page=1&channel=-1&source_id=1
来源：牛客网
一个非空表达式前缀可以表示成 a+ba+b 的形式。
如果后面接了一个 +x+x ，则变成 (a+b)+x(a+b)+x ；
如果后面接了一个 −x−x ，则变成 (a+b)+(−x)(a+b)+(−x) ；
如果后面接了一个 ∗x∗x ，则变成 a+b∗xa+b∗x ；
如果后面接了一个 /x/x ，则变成 a+b/xa+b/x 。
最后还是可以表示成 a+ba+b 的形式。
因此只需要遍历整棵树维护每个节点对应的 a+ba+b 即可。
坑点是减法的时候要加上一个模数防止出现负数，以及除法取模要用到乘法逆元。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#define mod 1000000007
#define maxn 100005
using namespace std;
int n, val[maxn], head[maxn], ver[2 * maxn], Next[2 * maxn], tot = 0;
string s;
long long a[maxn], b[maxn];
long long ans[maxn];
void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
long long fpow(long long a, long long b)
{
long long ans = 1;
for(; b; b >>= 1)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
long long inv(long long x)
{
return fpow(x, mod - 2);
}
void dfs(int x, int pre)
{
for(int i = head[x]; i; i = Next[i])
{
int y = ver[i];
char op = s[y - 2];
if(y == pre) continue;
if(op == '+')
{
a[y] = (a[x] + b[x]) % mod, b[y] = val[y];
}
else if(op == '-')
{
a[y] = (a[x] + b[x]) % mod, b[y] = (-val[y] + mod) % mod;
}
else if(op == '*')
{
a[y] = a[x], b[y] = b[x] * val[y] % mod;
}
else
{
a[y] = a[x], b[y] = b[x] * inv(val[y]) % mod;
}
dfs(y, x);
}
ans[x] = (a[x] + b[x]) % mod;
}
int main()
{
freopen("data.txt", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++) cin >> val[i];
for(int i = 1; i <= n - 1; i++)
{
int fa;
cin >> fa;
add(fa, i + 1);
add(i + 1, fa);
}
cin >> s;
a[1] = 0, b[1] = val[1];
dfs(1, 0);
for(int i = 1; i <= n; i++)
{
cout << ans[i] << ' ';
}
return 0;
}