题目描述：
给出一棵n个节点的树，每个点初始m值为1。
你有三种操作：
1.Add l r k ，将l到r路径上所有点m值加k。
2.Multi l r k ，将l到r路径上所有点m值乘k。
3.Query l r ，设x是l到r路径上的点，y是x的m值。假设有1~y共y个点，随机打乱，求形成错排的概率。
（k<=1000,n<=80000）
题解：
树剖正解？
（反正我用的dfs序+并查集）
首先1000^80000错排怎么搞啊？
要明白我们真正要的并不是错排数，而是错排数/阶乘。
打表后发现他是：
0.0,0.5,0.333333333,0.375,0.366666667,0.368055556,0.367857143,0.367881944,0.367879464
最后一位用的一般值。
（后来发现这个精度依然不够，要用错排递推直接打表。不然会卡精。）
树链怎么修改啊？
其实可以用单点修改……
重点在于一共只有80000个点，如果m值超过15就不用处理了，保留15位就够了……
所以单点最多修改80000*15次……
并查集维护。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; //lgl AK in NOIp #define N 80050 double num[15],tmp[15]; void init() { double now = 2; tmp[1]=0.0,tmp[2]=1.0; num[2]=0.5; for(int i=3;i<15;i++) { now*=(double)i; tmp[i]=(double)(i-1)*(tmp[i-1]+tmp[i-2]); num[i]=(double)tmp[i]/now; } } int n,hed[N],cnt,q; char ch[20]; struct EG { int to,nxt; }e[2*N]; void ae(int ff,int t) { e[++cnt].to = t; e[cnt].nxt = hed[ff]; hed[ff] = cnt; } struct aaafku { int s[2*N]; void ins(int x,int d) { while(x<2*N) { s[x]+=d; x+=(x&(-x)); } } int qry(int x) { int ret = 0; while(x) { ret+=s[x]; x-=(x&(-x)); } return ret; } }f[15]; int las[N]; int dep[N],siz[N],fa[N],son[N],top[N],typ[N]; int tin[N],tout[N],tim; void dfs1(int u,int ff) { tin[u]=++tim; typ[u]=1; siz[u]=1; dep[u]=dep[ff]+1; las[u]=u; f[1].ins(tin[u],1); for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to==ff)continue; fa[to]=u; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>siz[son[u]])son[u]=to; } tout[u]=tim; f[1].ins(tout[u]+1,-1); } void dfs2(int u,int tp) { top[u] = tp; if(!son[u])return ; dfs2(son[u],tp); for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to!=fa[u]&&to!=son[u]) dfs2(to,to); } } int get_lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } int get_las(int x) { if(las[x]==x)return x; return las[x]=get_las(las[x]); } void deala(int u,int k,int lim) { if(dep[u]<=lim)return ; f[typ[u]].ins(tin[u],-1); f[typ[u]].ins(tout[u]+1,1); typ[u] = min(14,typ[u]+k); f[typ[u]].ins(tin[u],1); f[typ[u]].ins(tout[u]+1,-1); deala(get_las(fa[u]),k,lim); if(typ[u]==14)las[u]=fa[u]; } void dealb(int u,int k,int lim) { if(dep[u]<=lim)return ; f[typ[u]].ins(tin[u],-1); f[typ[u]].ins(tout[u]+1,1); typ[u] = min(14,typ[u]*k); f[typ[u]].ins(tin[u],1); f[typ[u]].ins(tout[u]+1,-1); dealb(get_las(fa[u]),k,lim); if(typ[u]==14)las[u]=fa[u]; } int main() { // freopen("yuyuko.in","r",stdin); // freopen("yuyuko.out","w",stdout); init(); scanf("%d",&n); for(int ff,t,i=1;i<n;i++) { scanf("%d%d",&ff,&t); ae(ff,t),ae(t,ff); } dfs1(1,1),dfs2(1,1); scanf("%d",&q); for(int l,r,k,i=1;i<=q;i++) { scanf("%s",ch+1); if(ch[1]=='Q') { scanf("%d%d",&l,&r); int lca = get_lca(l,r); int ff = fa[lca]; double ans = 0.0; for(int j=1;j<15;j++) { int sum = f[j].qry(tin[l])+f[j].qry(tin[r])-f[j].qry(tin[lca])-f[j].qry(tin[ff]); ans+=(double)sum*num[j]; } printf("%.1lf ",ans); }else { scanf("%d%d%d",&l,&r,&k); int lca = get_lca(l,r); if(ch[1]=='A') { deala(las[l],k,dep[lca]); deala(las[r],k,dep[lca]-1); }else { dealb(las[l],k,dep[lca]); dealb(las[r],k,dep[lca]-1); } } } return 0; }