Luogu

LOJ

分析

LCT + 泰勒展开。

取 $x_0=0.5$ ，然后泰勒展开，发现后面的项的贡献很小，可以只保留 $13$ 项。

$\mathrm{LCT}$ 的每个节点维护该点函数的 $n$ 阶导数与子树的 $n$ 阶导数和，这样子查询就可以直接拿出来算。

至于 $n$ 阶导数怎么算...

• $sin'(x)=cos(x),\ cos'(x)=-sin(x)$
• $(e^x)'=e^x$
• $(ax+b)'=a,\ C'=0$
• $f\big(g(x)\big)'=f'\big(g(x)\big)\cdot g'(x)$

套公式大力算就行了（

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Link_Cut_Tree {
    double f[N][13],s[N][13];
    struct node { int op; double a,b; } d[N];
    int ch[N][2],fa[N],rev[N];
    int sta[N];

    inline double calc(int op,int n,double a,double b) {
        if (op==1) {
            double res;
            if (n%4==0) res=sin(a*0.5+b);
            else if (n%4==1) res=cos(a*0.5+b);
            else if (n%4==2) res=-sin(a*0.5+b);
            else res=-cos(a*0.5+b);
            return res*pow(a,n);
        } else if (op==2) return pow(a,n)*exp(a*0.5+b);
        else {
            if (!n) return a*0.5+b;
            else if (n==1) return a;
            else return 0;
        }
    }

    inline void calc(int x) {
        for (re int i=0;i<=12;++i)
            f[x][i]=calc(d[x].op,i,d[x].a,d[x].b);
    }

    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void reverse(int x) { swap(ch[x][0],ch[x][1]); rev[x]^=1; }

    inline void pushup(int x) {
        for (re int i=0;i<=12;++i)
            s[x][i]=f[x][i]+s[ch[x][0]][i]+s[ch[x][1]][i];
    }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }

    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(ch[y][1]==x),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y))
                rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }

    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x])
            splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x),splay(x),reverse(x); }
    inline int findroot(int x) {
        access(x),splay(x);
        while (ch[x][0]) pushdown(x),x=ch[x][0];
        return x;
    }
    inline void split(int x,int y) { makeroot(x),access(y),splay(y); }

    inline void link(int x,int y) { makeroot(x),fa[x]=y; }
    inline void cut(int x,int y) { split(x,y),ch[y][0]=fa[x]=0,pushup(y); }
    inline void modify(int x,int op,double a,double b) {
        access(x),splay(x); d[x]=(node){op,a,b};
        calc(x); pushup(x);
    }
} T;

int main() {
    int n=read(),m=read(); read();
    for (re int i=1;i<=n;++i) {
        T.d[i].op=read(); scanf("%lf%lf",&T.d[i].a,&T.d[i].b);
        T.calc(i);
    }
    while (m--) {
        char op[10]; scanf("%s",op);
        if (op[0]=='a') {
            int u=read()+1,v=read()+1;
            T.link(u,v);
        } else if (op[0]=='d') {
            int u=read()+1,v=read()+1;
            T.cut(u,v);
        } else if (op[0]=='m') {
            int u=read()+1,f=read();
            double a,b; scanf("%lf%lf",&a,&b);
            T.modify(u,f,a,b);
        } else if (op[0]=='t') {
            int u=read()+1,v=read()+1;
            double x; scanf("%lf",&x);
            if (T.findroot(u)!=T.findroot(v)) puts("unreachable");
            else {
                T.split(u,v);
                double pw=1,fac=1,ans=0; x-=0.5;
                for (re int i=0;i<=12;++i,pw*=x,fac*=i)
                    ans+=pw*T.s[v][i]/fac;
                printf("%.9lf\n",ans);
            }
        }
    }
    return 0;
}