前置知识：复合函数求导，LCT，泰勒公式
什么你不会泰勒公式？我也不会题面底下都告诉你了，所以就不困难了，直接套公式就好。
首先看题目要求维护什么：
- 连边，删边，保证是一个森林。
- 修改点的函数。
- 对一条树上路径的函数值求和。（$x$ 值相同）
通过这三点可以看出这是一道动态树问题，可以用 LCT 维护。
但是问题是，三种函数分别是正弦函数、指数函数和一次函数，不能直接加减合并，怎么办？
这时候就到了考验读题数学能力的时候了，我们可以用泰勒展开将前两个函数都展开为多项式函数，就可以直接进行相加减了。
我们来看题目中给出的公式：
\[f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(x_0)(x-x_0)^k}{k!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b]\]我们取 $x_0=0$，那么其实展开就是：
\[\begin{aligned} f(x)&=f'(0)+\frac{f'(0)x}{1!}+\frac{f''(0)x^2}{2!}+\cdots+\frac{f^{(n)}(0)x^n}{n!}\\ &=\sum_{k=0}^n \frac{f^{(k)}(0)x^k}{k!} \end{aligned}\]所以我们来看观察前两个函数的导数：
（求导为高二数学知识，如果不会求导的，请左转百度）
$f(x)=\sin(ax+b)$
我们多列几项来找规律：
\[\begin{aligned} f(x)&=\sin(ax+b)\\ f^{(1)}(x)&=a\cos(ax+b)\\ f^{(2)}(x)&=-a^2\sin(ax+b)\\ f^{(3)}(x)&=-a^3\cos(ax+b)\\ f^{(4)}(x)&=a^4\sin(ax+b)\\ f^{(5)}(x)&=a^5\cos(ax+b) \end{aligned}\]我们发现，它的 $n$ 阶导数为 $a^n$ 乘上一个以四为周期的函数，即：
\[f^{(n)}(x)=\begin{cases} a^n\sin(ax+b) &(x \bmod 4=0)\\ a^n\cos(ax+b) &(x \bmod 4=1)\\ -a^n\sin(ax+b) &(x \bmod 4=2)\\ -a^n\cos(ax+b) &(x \bmod 4=3)\\ \end{cases}\]接下来带入上面的式子展开就好啦！
static Poly Sin(ld a, ld b) {
f[0] = sin(b);
f[1] = cos(b);
f[2] = -sin(b);
f[3] = -cos(b);
Poly A; // Poly 为多项式
ld y = 1;
for (int i = 0; i <= 20; i++) {
A.a[i] = f[i % 4] * y / fac[i];
y *= a;
}
return A;
}
$f(x)=\text e^{ax+b}$
同样的，来找规律：
\[\begin{aligned} f(x)&=\text e^{ax+b}\\ f^{(1)}(x)&=a\text e^{ax+b}\\ f^{(2)}(x)&=a^2\text e^{ax+b}\\ f^{(3)}(x)&=a^3\text e^{ax+b}\\ f^{(4)}(x)&=a^4\text e^{ax+b}\\ f^{(5)}(x)&=a^5\text e^{ax+b} \end{aligned}\]这个比正弦函数要简单些，列出来就是：
\[f^{(n)}(x)=a^n\text e^{ax+b}\]static Poly Exp(ld a, ld b) {
Poly A;
ld y = 1;
ld q = exp(b);
for (int i = 0; i <= 20; i++) {
A.a[i] = q * y / fac[i];
y *= a;
}
return A;
}
接下来用 LCT 来维护这个多项式函数（就直接把对应系数加起来就好，不要看到多项式就害怕），这题就结束了！
上代码！
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
ld ans1, ans2;
ld fac[50];
ld f[6];
struct Poly {
ld a[30];
Poly() {
memset(a, 0, sizeof a);
}
Poly operator+(Poly b) {
Poly c;
for (int i = 0; i <= 20; i++)
// 实际上展开10项就足以通过本题，为了保险起见多展开一些。
c.a[i] = a[i] + b.a[i];
return c;
}
ld operator()(ld x) {
ld ans = 0;
ld y = 1;
for (int i = 0; i <= 20; i++) {
ans += y * a[i];
y *= x;
}
return ans;
}
static Poly Sin(ld a, ld b) {
f[0] = sin(b);
f[1] = cos(b);
f[2] = -sin(b);
f[3] = -cos(b);
Poly A;
ld y = 1;
for (int i = 0; i <= 20; i++) {
A.a[i] = f[i % 4] * y / fac[i];
y *= a;
}
return A;
}
static Poly Exp(ld a, ld b) {
Poly A;
ld y = 1;
ld q = exp(b);
for (int i = 0; i <= 20; i++) {
A.a[i] = q * y / fac[i];
y *= a;
}
return A;
}
static Poly Line(ld a, ld b) {
Poly A; A.a[0] = b, A.a[1] = a;
return A;
}
};
const int MAXN = 200005;
struct LCT {
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
int ch[MAXN][2], fa[MAXN];
bool tag[MAXN];
Poly v[MAXN], sum[MAXN];
bool ident(int x) { return rc(fa[x]) == x; }
bool nroot(int x) { return lc(fa[x]) == x || rc(fa[x]) == x; }
void reverse(int x) { swap(lc(x), rc(x)), tag[x] ^= 1; }
void pushDown(int x) {
if (tag[x])
reverse(lc(x)), reverse(rc(x)), tag[x] = 0;
}
void pushUp(int x) { sum[x] = sum[lc(x)] + sum[rc(x)] + v[x]; }
void rotate(int x) {
int f = fa[x], ff = fa[f];
int a = ident(x), b = ident(f);
if (nroot(f)) ch[ff][b] = x;
fa[x] = ff;
ch[f][a] = ch[x][!a];
fa[ch[x][!a]] = f;
ch[x][!a] = f;
fa[f] = x;
pushUp(f), pushUp(x);
}
void splay(int x) {
stack<int> st; int y = x; st.push(x);
while (nroot(y)) st.push(y = fa[y]);
while (!st.empty()) pushDown(st.top()), st.pop();
while (nroot(x)) {
if (nroot(fa[x])) {
rotate(ident(x) == ident(fa[x]) ? fa[x] : x);
}
rotate(x);
}
pushUp(x);
}
void access(int x) {
for (int y = 0; x; x = fa[y = x]) {
splay(x), rc(x) = y, pushUp(x);
}
}
void makeRoot(int x) {
access(x), splay(x), reverse(x);
}
int findRoot(int x) {
access(x), splay(x);
while (lc(x)) pushDown(x), x = lc(x);
splay(x);
return x;
}
void split(int x, int y) {
makeRoot(x), access(y), splay(y);
}
void link(int x, int y) {
makeRoot(x), fa[x] = y;
}
void cut(int x, int y) {
makeRoot(x), findRoot(y), rc(x) = fa[y] = 0;
}
}lct;
int n, m;
char type[10];
int main() {
fac[0] = 1;
for (int i = 1; i <= 30; i++) {
fac[i] = fac[i - 1] * i;
}
scanf("%d%d%s", &n, &m, type);
for (int i = 1; i <= n; i++) {
int f;
ld a, b;
scanf("%d%lf%lf", &f, &a, &b);
if (f == 1) lct.v[i] = Poly::Sin(a, b);
if (f == 2) lct.v[i] = Poly::Exp(a, b);
if (f == 3) lct.v[i] = Poly::Line(a, b);
lct.pushUp(i);
}
for (int i = 1; i <= m; i++) {
scanf("%s", type);
if (type[0] == 'a') {
int u, v; scanf("%d%d", &u, &v);
u++, v++;
lct.link(u, v);
}
if (type[0] == 'd') {
int u, v; scanf("%d%d", &u, &v);
u++, v++;
lct.cut(u, v);
}
if (type[0] == 'm') {
int c, f; ld a, b; scanf("%d%d%lf%lf", &c, &f, &a, &b);
c++;
lct.splay(c);
if (f == 1) lct.v[c] = Poly::Sin(a, b);
if (f == 2) lct.v[c] = Poly::Exp(a, b);
if (f == 3) lct.v[c] = Poly::Line(a, b);
lct.pushUp(c);
}
if (type[0] == 't') {
int u, v; ld x; scanf("%d%d%lf", &u, &v, &x);
u++, v++;
lct.makeRoot(u);
if (lct.findRoot(v) != u) {
printf("unreachable\n");
} else {
lct.split(u, v);
printf("%.8le\n", lct.sum[v](x));
}
}
}
return 0;
}
