bzoj5020
\[答案误差只要小于 10^{-7}\]
题解
Taylor展开式:
\[若f(x)的n阶导数在[a, b]内连续，则f(x)在x_{0}\in[a, b]可表示为\]
\[f(x)=\sum_{i=0}^{n} \frac{ f^{(n)}(x_{0})(x-x_{0})^{i} }{i!} + \Theta((x-x_{0})^{n})\]
\[其中f^{(n)}表示函数f的n阶导数，\Theta((x-x_{0})^{n})为误差\]
\[对于这道题，令x_{0}=0，求大约12阶导数即可保证误差小于10^{-7}\]
用Taylor展开式可以直接把路径上的函数合并
直接开12变量个记录每一阶的导数，用LCT维护，统计答案用Taylor展开式计算
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(400010);
const double E = pow(2, 1.0 / log(2));
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, m;
namespace LCT{
int ch[2][_], fa[_], rev[_], S[_];
double w[17][_], sum[17][_];
IL bool Son(RG int x){ return ch[1][fa[x]] == x; }
IL bool Isroot(RG int x){ return ch[0][fa[x]] != x && ch[1][fa[x]] != x; }
IL void Update(RG int x){ for(RG int i = 0; i < 16; ++i) sum[i][x] = sum[i][ch[0][x]] + sum[i][ch[1][x]] + w[i][x]; }
IL void Pushdown(RG int x){ if(!rev[x]) return; rev[x] ^= 1; rev[ch[0][x]] ^= 1; rev[ch[1][x]] ^= 1; swap(ch[0][x], ch[1][x]); }
IL void Rot(RG int x){
RG int y = fa[x], z = fa[y], c = Son(x);
if(!Isroot(y)) ch[Son(y)][z] = x; fa[x] = z;
ch[c][y] = ch[!c][x]; fa[ch[c][y]] = y;
ch[!c][x] = y; fa[y] = x; Update(y);
}
IL void Splay(RG int x){
RG int top = 0; S[++top] = x;
for(RG int i = x; !Isroot(i); i = fa[i]) S[++top] = fa[i];
while(top) Pushdown(S[top--]);
for(RG int y = fa[x]; !Isroot(x); Rot(x), y = fa[x])
if(!Isroot(y)) Son(x) ^ Son(y) ? Rot(x) : Rot(y);
Update(x);
}
IL void Access(RG int x){ for(RG int y = 0; x; y = x, x = fa[x]) Splay(x), ch[1][x] = y, Update(x); }
IL int Findroot(RG int x){ Access(x); Splay(x); while(ch[0][x]) x = ch[0][x]; return x; }
IL void Makeroot(RG int x){ Access(x); Splay(x); rev[x] ^= 1; }
IL void Split(RG int x, RG int y){ Makeroot(x); Access(y); Splay(y); }
IL void Link(RG int x, RG int y){ Makeroot(x); fa[x] = y; }
IL void Cut(RG int x, RG int y){ Split(x, y); ch[0][y] = fa[x] = 0; }
IL double Query(RG int x, RG int y, RG double xx){
Split(x, y);
RG double ans = sum[0][y], fac = 1, xxx = 1;
for(RG int i = 1; i < 16; i++) fac *= i, xxx *= xx, ans += sum[i][y] / fac * xxx;
return ans;
}
IL void Calc(RG int x, RG int f, RG double a, RG double b){
for(RG int i = 0; i < 16; ++i) w[i][x] = 0;
if(f == 3) w[0][x] = b, w[1][x] = a;
else if(f == 1){
RG double aa = 1; w[0][x] = sin(b);
for(RG int i = 1; i < 16; ++i){
aa *= a;
if(i % 4 == 1) w[i][x] = aa * cos(b);
else if(i % 4 == 2) w[i][x] = -aa * sin(b);
else if(i % 4 == 3) w[i][x] = -aa * cos(b);
else w[i][x] = aa * sin(b);
}
}
else{
w[0][x] = pow(E, b);
for(RG int i = 1; i < 16; ++i) w[i][x] = w[i - 1][x] * a;
}
}
IL void Work(){
RG char c; RG int u, v, p, f; RG double x, a, b;
for(RG int i = 1; i <= n; ++i) f = Read(), scanf("%lf%lf", &a, &b), Calc(i, f, a, b);
while(m--){
scanf(" %c", &c);
if(c == 'a') u = Read() + 1, v = Read() + 1, Link(u, v);
else if(c == 'd') u = Read() + 1, v = Read() + 1, Cut(u, v);
else if(c == 'm') p = Read() + 1, f = Read(), scanf("%lf%lf", &a, &b), Calc(p, f, a, b), Splay(p);
else{
u = Read() + 1; v = Read() + 1; scanf("%lf", &x);
if(Findroot(u) != Findroot(v)) puts("unreachable");
else printf("%.8e\n", Query(u, v, x));
}
}
}
}
int main(RG int argc, RG char *argv[]){
n = Read(); m = Read(); Read();
LCT::Work();
return 0;
}