首先发现有连边和删边的操作，所以我们肯定要用\(LCT\)来进行维护。
接下来考虑如何进行\(LCT\)上的信息合并。
\(f=1\),则函数为\(f(x)=sin(ax+b)\)
\(f=2\),则函数为\(f(x)=e^{ax+b}\)
\(f=3\),则函数为\(f(x)=ax+b\)
这道题中的信息为这三个函数，因为\(sin(ax+b)\)和\(e^{ax+b}\)不好处理，所以用泰勒展开都其处理为多项式的形式，再进行多项式的合并即可。
泰勒公式：
\[f(x)=\sum_{i=0}^{n} \frac{f^{(i)}(x_0)\times(x-x_0)^i}{i!}\]
我们让\(x_0=0\)，得：
\[f(x)=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i\]
根据求导的知识，得：
\[(\sin x)'=\cos x\]
\[(\cos x)'=-\sin x\]
\[(-\sin x)'=-\cos x\]
\[(-\cos x)'=\sin x\]
\[(e^x)'=e^x\]
同时再应用链式法则。
对\(sin(ax+b)\)进行泰勒展开得：
\[sin(ax+b)=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i\]
其中，\(f^{(i)}(0)\)为：
\[f^{(i)}(0)=\begin{cases}\sin(b)\ (i\mod4=0)\\\cos(b)\ (i\mod4=1)\\-\sin(b)\ (i\mod4=2)\\-\cos(b)\ (i\mod4=3)\end{cases}\]
对\(e^{ax+b}\)进行泰勒展开得：
\[e^{ax+b}=\sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!}x^i=\sum_{i=0}^{n} \frac{a^ie^b}{i!}x^i\]
解决了信息合并后，修改查询什么的都是\(LCT\)的基本操作了，然后这道题就做完了。
实现细节看代码吧。
\(code:\)
#include<bits/stdc++.h>
#define maxn 100010
#define maxm 20
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m;
char type[10];
int fa[maxn],ch[maxn][2],rev[maxn],f[maxn];
double fac[maxm],sum[maxn][maxm],a[maxn],b[maxn];
bool check(int x)
{
return ch[fa[x]][1]==x;
}
void pushr(int x)
{
rev[x]^=1;swap(ch[x][0],ch[x][1]);
}
void pushup(int x)
{
for(int i=0;i<=15;++i)
sum[x][i]=sum[ch[x][0]][i]+sum[ch[x][1]][i];
if(f[x]==1)
{
double val=1,s=sin(b[x]),c=cos(b[x]);
for(int i=0;i<=15;i+=4)
{
sum[x][i]+=s*val,val*=a[x];
sum[x][i+1]+=c*val,val*=a[x];
sum[x][i+2]-=s*val,val*=a[x];
sum[x][i+3]-=c*val,val*=a[x];
}
}
if(f[x]==2)
{
double val=exp(b[x]);
for(int i=0;i<=15;++i) sum[x][i]+=val,val*=a[x];
}
if(f[x]==3) sum[x][1]+=a[x],sum[x][0]+=b[x];
}
void pushdown(int x)
{
if(!rev[x]) return;
pushr(ch[x][0]),pushr(ch[x][1]);
rev[x]=0;
}
bool notroot(int x)
{
return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=check(x),w=ch[x][k^1];
if(notroot(y)) ch[z][check(y)]=x;
fa[x]=z;
ch[y][k]=w;
if(w) fa[w]=y;
ch[x][k^1]=y;
fa[y]=x;
pushup(y);
}
void all(int x)
{
if(notroot(x)) all(fa[x]);
pushdown(x);
}
void splay(int x)
{
all(x);
for(int y;notroot(x);rotate(x))
if(notroot(y=fa[x]))
rotate(check(x)^check(y)?x:y);
pushup(x);
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,pushup(x);
}
void makeroot(int x)
{
access(x),splay(x),pushr(x);
}
void split(int x,int y)
{
makeroot(x),access(y),splay(y);
}
int findroot(int x)
{
access(x),splay(x);
while(ch[x][0]) x=ch[x][0];
splay(x);
return x;
}
void link(int x,int y)
{
makeroot(x),fa[x]=y;
}
void cut(int x,int y)
{
split(x,y),fa[x]=ch[y][0]=0;
}
void modify(int x,int nf,double na,double nb)
{
makeroot(x);
f[x]=nf,a[x]=na,b[x]=nb;
}
double query(int x,int y,double q)
{
double ans=0,now=1;
split(x,y);
for(int i=0;i<=15;++i)
ans+=sum[y][i]*now/fac[i],now*=q;
return ans;
}
void init()
{
fac[0]=1;
for(int i=1;i<=18;++i) fac[i]=fac[i-1]*i;
}
int main()
{
init();
read(n),read(m);
scanf("%s",type);
for(int i=1;i<=n;++i)
read(f[i]),scanf("%lf%lf",&a[i],&b[i]);
while(m--)
{
int x,y,nf;
double na,nb,q;
scanf("%s",type);
if(type[0]=='a')
read(x),read(y),link(x+1,y+1);
if(type[0]=='d')
read(x),read(y),cut(x+1,y+1);
if(type[0]=='m')
{
read(x),read(nf),x++;
scanf("%lf%lf",&na,&nb);
modify(x,nf,na,nb);
}
if(type[0]=='t')
{
read(x),read(y),x++,y++;
scanf("%lf",&q);
if(findroot(x)!=findroot(y))
{
puts("unreachable");
continue;
}
printf("%.10lf\n",query(x,y,q));
}
}
return 0;
}题解 洛谷 P4546 【[THUWC2017]在美妙的数学王国中畅游】
原文：https://www.cnblogs.com/lhm-/p/12232243.html