【题解】「THUWC 2017」在美妙的数学王国中畅游 LCT loj2289 —Qiuly

挺傻一题，是我蠢了。

有请喜闻乐见的泰勒公式：
$$
f(x)=\sum_{i=0}^{n}\frac{f^{(i)}(x_0)\cdot (x-x_0)}{i!}
$$

要求精度达到 $10^{-7}$ ，$n$ 取 $15$ 左右就够了。为了方便，令这里的 $x_0=0$ 。

每个点维护一个多项式，多项式的第 $i$ 项的值就是 $f^{(i)}(0)$ ，然后现在就是需要维护一下一条链上的每一项的和，显然一个 $\rm{LCT}$ 。

求导的话很简单相信大家都会：

$type=1$ ：
$$
f^{(i)}(x_0)=
\begin{cases}
\sin(x)\ \ \ \ \ \ \ \ i\ \rm{mod}\ 4=0\\
\cos(x)\ \ \ \ \ \ \ \ i\ \rm{mod}\ 4=1\\
-\sin(x)\ \ \ \ \ i\ \rm{mod}\ 4=2\\
-\cos(x)\ \ \ \ \ i\ \rm{mod}\ 4=3\\
\end{cases}
$$
$type=2$ ：
$$
f^{(i)}(x_0)=a^ie^b
$$
$type=3$ ：
$$
f^{(0)}(x_0)=b_u\\ f^{(1)}(x_0)=a_u
$$
需要注意一下后面的常数 $C$ 。

每一次维护一下即可。

Code：

#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
int n,m,F[N];
double A[N],B[N],fac[20];
char op[20],type[5];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Link_Cut_Tree {
    int fa[N],rev[N],hep[N],ch[N][2];
    double sum[N][20];
    inline int get(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
    inline void flip(int x) {swap(ch[x][0],ch[x][1]),rev[x]^=1;}
    inline void pushdown(int x) {
        if(!rev[x]) return;rev[x]=0;
        if(ch[x][0]) flip(ch[x][0]);
        if(ch[x][1]) flip(ch[x][1]);
    } 
    inline void pushup(int x) {
        for(int i=0;i<16;++i) sum[x][i]=sum[ch[x][0]][i]+sum[ch[x][1]][i];
        if(F[x]==1) {
            double Sin=sin(B[x]),Cos=cos(B[x]),Const=1.0;
            for(int i=0;i<16;i+=4) {
                sum[x][i]+=Sin*Const,Const*=A[x];
                sum[x][i+1]+=Cos*Const,Const*=A[x];
                sum[x][i+2]-=Sin*Const,Const*=A[x];
                sum[x][i+3]-=Cos*Const,Const*=A[x];
            }
        } else if(F[x]==2) {
            double E=exp(B[x]);sum[x][0]+=E;
            for(int i=1;i<16;++i) E*=A[x],sum[x][i]+=E;
        } else if(F[x]==3) sum[x][0]+=B[x],sum[x][1]+=A[x];
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=ch[y][1]==x,v=ch[x][!k];
        if(get(y)) ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
        if(v) fa[v]=y;fa[y]=x,fa[x]=z;pushup(y);
    }
    inline void Splay(int x) {
        int y=x,top=0;hep[++top]=y;
        while(get(y)) hep[++top]=y=fa[y];
        while(top) pushdown(hep[top--]);
        while(get(x)) {
            y=fa[x],top=fa[y];
            if(get(y)) rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
            rotate(x);
        }pushup(x);
    }
    inline void Access(int x) {for(int y=0;x;x=fa[y=x]) Splay(x),ch[x][1]=y,pushup(y);}
    inline void makeroot(int x) {Access(x),Splay(x),flip(x);}
    inline void split(int x,int y) {makeroot(x),Access(y),Splay(y);}
    inline int findroot(int x) {
        Access(x),Splay(x);
        while(ch[x][0]) pushdown(x),x=ch[x][0];
        Splay(x);return x;
    }
    inline void link(int x,int y) {makeroot(x),fa[x]=y;}
    inline void cut(int x,int y) {split(x,y),fa[x]=ch[y][0]=0;}
}using namespace Link_Cut_Tree;

int main() {
    freopen("2289.in","r",stdin);
    freopen("2289.out","w",stdout);
    IN(n),IN(m),scanf("%s",type),fac[0]=1;
    for(int i=1;i<16;++i) fac[i]=1.0*fac[i-1]*i;
    for(int i=1;i<=n;++i) IN(F[i]),scanf("%lf%lf",&A[i],&B[i]);
    while(m--) {
        scanf("%s",op);
        if(op[0]=='m') {
            int c,f;double a,b;IN(c),++c,IN(f),scanf("%lf%lf",&a,&b);
            Splay(c),F[c]=f,A[c]=a,B[c]=b,pushup(c);
        } else {
            int u,v;IN(u),IN(v),++u,++v;
            if(op[0]=='a') link(u,v);    
            else if(op[0]=='d') cut(u,v);
            else if(op[0]=='t') {
                double x=1.0,iq;scanf("%lf",&iq);
                if(findroot(u)^findroot(v)) {puts("unreachable");continue;}
                split(u,v);
                double ans=0.0;
                for(int i=0;i<16;++i) ans+=sum[v][i]*x/fac[i],x*=iq;
                printf("%.8e\n",ans);
            }
        }
    }
    return 0;
}