传送门

不多bb，直接安利

一眼$LCT$，然而乍一看一堆函数求和没得搞。

题目下面给出了泰勒展开的式子。于是可以对$\sin(ax+b)$和$e^{ax+b}$泰勒展开，用多项式拟合函数。

先求个导：

  • $(\sin(ax+b))^{(n)}=\begin{cases}a^n\sin(ax+b)&n\bmod4=0\\a^n\cos(ax+b)&n\bmod4=1\\ -a^n\sin(ax+b)&n\bmod4=2\\ -a^n\cos(ax+b)&n\bmod4=3\end{cases}$
  • $(e^{ax+b})^{(n)}=a^ne^{ax+b}$

至于$\xi,x_0$的取值，代个$0$就很方便。

现在要搞的就是一堆多项式求和，直接系数相加就能维护了。

由于分母上是阶乘，增长非常快，实测展开到$11$次项就能过。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 100005
#define inf 0x3f3f3f3f
#define tp 11

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
struct Poly{
    double c[tp+1];
    Poly(int t=3,double a=0,double b=0){
        if(t==1){
            double S=sin(b),C=cos(b),base=1;
            for(register int i=0;i<=tp;i+=2,S=-S,C=-C)c[i]=base*S,base*=a,c[i+1]=base*C,base*=a;
        }
        else if(t==2){
            double e=exp(b),base=1;
            for(register int i=0;i<=tp;++i)c[i]=e*base,base*=a;
        }
        else{
            c[0]=b,c[1]=a;
            for(register int i=2;i<=tp;++i)c[i]=0;
        }
    }
    Poly operator + (const Poly &x){
        Poly ans;
        for(register int i=0;i<=tp;++i)ans.c[i]=c[i]+x.c[i];
        return ans;
    }
}sum[maxn],dat[maxn];
#define son(x,y) son[x][y]
#define ls(x) son(x,0)
#define rs(x) son(x,1)
#define whson(x) (son(fa[x],1)==x)
#define root(x) (son(fa[x],0)!=x&&son(fa[x],1)!=x)
int son[maxn][2],fa[maxn],rev[maxn];
inline void update(int node){sum[node]=sum[ls(node)]+sum[rs(node)]+dat[node];}
inline void adde(int s,int f,bool wh){
    if(s)fa[s]=f;
    son(f,wh)=s;
}
inline void rotate(int x){
    int f=fa[x],gf=fa[f],wh=whson(x);
    if(!root(f))son(gf,whson(f))=x;
    fa[x]=gf;
    adde(son(x,wh^1),f,wh);
    adde(f,x,wh^1);
    update(f),update(x);
}
inline void rever(int node){
    swap(ls(node),rs(node));
    rev[node]^=1;
}
inline void pushdown(int node){
    if(rev[node]){
        if(ls(node))rever(ls(node));
        if(rs(node))rever(rs(node));
        rev[node]=0;
    }
}
inline void pushtag(int node){
    if(!root(node))pushtag(fa[node]);
    pushdown(node);
}
inline void splay(int x){
    pushtag(x);
    int y;
    while(!root(x)){
        y=fa[x];
        if(!root(y))rotate(whson(x)^whson(y)?x:y);
        rotate(x);
    }
}
void access(int x){
    for(register int y=0;x;y=x,x=fa[x])
        splay(x),rs(x)=y,update(x);
}
void makeroot(int x){
    access(x),splay(x),rever(x);
}
int findroot(int x){
    access(x),splay(x);
    while(ls(x))pushdown(x),x=ls(x);
    splay(x);
    return x;
}
void link(int x,int y){
    makeroot(x),fa[x]=y;
}
void cut(int x,int y){
    makeroot(x),access(y),splay(y);
    fa[x]=ls(y)=0,update(y);
}
void modify(int x,int t,double a,double b){
    splay(x),dat[x]=Poly(t,a,b),update(x);
}
void query(int x,int y,double z){
    makeroot(x);
    if(findroot(y)!=x){puts("unreachable");return;}
    splay(y);
    double ans=0,base=1,fac=1;
    for(register int i=0;i<=tp;++i,fac*=i)ans+=base*sum[y].c[i]/fac,base*=z;
    printf("%.9lf\n",ans);
}
int main(){
    int n=read(),m=read(),x,y;
    double a,b;
    char s[10];
    scanf("%s",s);
    for(register int i=1;i<=n;++i){
        x=read();
        scanf("%lf%lf",&a,&b);
        dat[i]=sum[i]=Poly(x,a,b);
    }
    while(m--){
        scanf("%s",s),x=read(),y=read();
        if(s[0]=='a')link(x+1,y+1);
        else if(s[0]=='d')cut(x+1,y+1);
        else if(s[0]=='m')scanf("%lf%lf",&a,&b),modify(x+1,y,a,b);
        else scanf("%lf",&a),query(x+1,y+1,a);
    }
}