题解
我们发现，题目告诉我们这个东西就是一个lct
首先，如果只有3，问题就非常简单了，我们算出所有a的总和，所有b的总和就好了
要是1和2也是多项式就好了……其实可以！也就是下面泰勒展开的用处，我们可以用一个多项式取逼近这个函数，而且，多项式次数越高越准确，我们大概到13次多项式就好了
如何创造出这个多项式呢，泰勒展开的式子是这样的
\(\sum_{i = 0}^{n} \frac{f^{(i)}(x_{0}) (x - x_{0})^{i}}{i!}\)
其中\(f^{(i)}(x)\)表示\(f(x)\)的\(i\)阶导数
然后问题就变成了维护13个值的和的lct了
然后，如何求导
根据高中选修2-2
我们有
\(f(g(x)) = g'(x)f'(g(x))\)
对于第一类型的函数
\(sin^{(1)}(ax b) = a\cdot cos(ax b)\)
\(sin^{(2)}(ax b) = -a^{2}\cdot sin(ax b)\)
\(sin^{(3)}(ax b) = -a^{3}\cdot cos(ax b)\)
\(sin^{(4)}(ax b) = a^{4}\cdot sin(ax b)\)
4次一个轮回
对于第二类型的函数
\(f(x)^{(1)} = a\cdot e^{ax b}\)
\(f(x)^{(2)} = a^{2}\cdot e^{ax b}\)
\(f(x)^{(n)} = a^{n}\cdot e^{ax b}\)
= =lct的cut是，先把一个点变成根，另一个点access一下，再splay成根，然后断掉根节点的左儿子
代码
#include
#include
#include
#include
#include
#include
//#define ivorysi
#define pb push_back
#define maxn 100005
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long int64;
typedef double db;
int n,m;
char s[25];
db fac[20];
struct tr {
tr *lc,*rc,*fa;
db sum[14],f[14];
bool rev;
void update() {
for(int i = 0 ; i <= 13 ; i) sum[i] = f[i];
if(lc) for(int i = 0 ; i <= 13 ; i) sum[i] = lc->sum[i];
if(rc) for(int i = 0 ; i <= 13 ; i) sum[i] = rc->sum[i];
}
void reverse() {
rev ^= 1;swap(lc,rc);
}
void pushdown() {
if(rev) {
if(lc) lc->reverse();
if(rc) rc->reverse();
rev = 0;
}
}
}*tr[maxn];
bool which(tr *u) {
return u == u->fa->rc;
}
bool isroot(tr *u) {
if(!u->fa) return 1;
return u->fa->rc != u && u->fa->lc != u;
}
void rotate(tr *u) {
tr *v = u->fa,*w = v->fa;
tr *b = u == v->lc ? u->rc : u->lc;
if(!isroot(v)) (v == w->lc ? w->lc : w->rc) = u;
u->fa = w;v->fa = u;
if(b) b->fa = v;
if(u == v->lc) v->lc = b,u->rc = v;
else v->rc = b,u->lc = v;
v->update();
}
void splay(tr *u) {
static tr* que[maxn];
int tot = 0;tr *x;
for(x = u ; !isroot(x) ; x = x->fa) que[ tot] = x;
que[ tot] = x;
for(int i = tot ; i >= 1 ; --i) que[i]->pushdown();
while(!isroot(u)) {
if(!isroot(u->fa)) {
if(which(u->fa) == which(u)) rotate(u->fa);
else rotate(u);
}
rotate(u);
}
u->update();
}
void access(tr *u) {
for(tr *x = null ; u ; x = u, u = u->fa) {
splay(u);
u->rc = x;
u->update();
}
}
tr* findroot(tr *u){
access(u);splay(u);
tr *res = u;
res->pushdown();
while(res->lc) {res = res->lc;res->pushdown();}
return res;
}
void makeroot(tr *u) {access(u);splay(u);u->reverse();}
void link(tr *u,tr *v) {makeroot(u);u->fa = v;}
void cut(tr *u,tr *v) {makeroot(u);access(v);splay(v);v->lc = u->fa = 0;v->update();}
db select(tr *u,tr *v,db x) {
makeroot(u);access(v);splay(u);
db res = 0,t = 1;
for(int i = 0 ; i <= 13 ; i) {
res = t * u->sum[i];
t *= x;
}
return res;
}
void change(tr *u,int ty,db a,db b) {
makeroot(u);
memset(u->f,0,sizeof(u->f));
if(ty == 1) {
db x = 1;
for(int i = 0 ; i <= 13 ; i) {
if(i % 4 == 0) u->f[i] = x * sin(b) / fac[i];
if(i % 4 == 1) u->f[i] = x * cos(b) / fac[i];
if(i % 4 == 2) u->f[i] = -x * sin(b) / fac[i];
if(i % 4 == 3) u->f[i] = -x * cos(b) / fac[i];
x *= a;
}
}
else if(ty == 2) {
db v = exp(b),x = 1;
for(int i = 0 ; i <= 13 ; i) {u->f[i] = v * x / fac[i];x *= a;}
}
else {
u->f[1] = a;u->f[0] = b;
}
u->update();
}
void solve() {
scanf("%d%d",&n,&m);
scanf("%s",s 1);
fac[0] = 1;
for(int i = 1 ; i <= 13 ; i) fac[i] = fac[i - 1] * i;
int f,u,v;db a,b;
for(int i = 1 ; i <= n ; i) {
tr[i] = new tr;tr[i]->lc = tr[i]->rc = tr[i]->fa = 0;
scanf("%d%lf%lf",&f,&a,&b);
change(tr[i],f,a,b);
}
for(int i = 1 ; i <= m ; i) {
scanf("%s",s 1);
if(s[1] == 'a' || s[1] == 'd') {
scanf("%d%d",&u,&v); u; v;
if(s[1] == 'a') link(tr[u],tr[v]);
if(s[1] == 'd') cut(tr[u],tr[v]);
}
else if(s[1] == 'm') {
scanf("%d%d%lf%lf",&u,&f,&a,&b); u;
change(tr[u],f,a,b);
}
else {
scanf("%d%d%lf",&u,&v,&a); u; v;
if(findroot(tr[u]) != findroot(tr[v])) puts("unreachable");
else printf("%.8e\n",select(tr[u],tr[v],a));
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
solve();
return 0;
}