一道神仙LCT题，思路清奇的一批。并且一些维护改变了我对LCT之前比较浅薄单一的认知，实在是一道启发心智的好题。同时这题因为不能迅速的维护很多状态，所以不能使用makeroot来改变树的结构，以免引起错误。所以基础模板也有别于普通模板。大部分的题解都注释在代码里了，应该还好。未完待续
#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define son(p,b) tree[p].child[b]
using namespace std;
typedef long long ll;
const int N=2e6+5;
struct node{
int child[2],fa;
ll sum,ans,ad,de,all,size;
//ans 答案 ，de 虚子树大小平方和 ，ad 虚子树内部答案和 ，all 不包含虚子树内size*a[k]的和
//size 所有虚子树大小和 ，sum 所有子树大小和
}tree[N];
int n,m,a[N];
//Splay part
inline void upd(int p){
tree[p].sum=tree[son(p,0)].sum+tree[son(p,1)].sum+tree[p].size;
//实子树大小的和和虚子树的和
tree[p].ans=tree[son(p,0)].ans+tree[son(p,1)].ans+tree[p].ad//左右实子树和虚子树答案
+(tree[p].size*tree[p].size-tree[p].de)*a[p]//拆开看
+2LL*tree[p].size*tree[son(p,1)].sum*a[p]//右子树是原树的子孙，选虚树中的和右子树组合lca为p
+2LL*tree[son(p,0)].all*(tree[p].sum-tree[son(p,0)].sum);//左子树是原树的祖先
tree[p].all=tree[son(p,0)].all+tree[son(p,1)].all+tree[p].size*a[p];
//实子树的虚子树的答案和（实子树包含了下面所有的虚子树的答案）和自己虚子树lca为p的贡献
//根据定义直接得出
}
inline int son_check(int p){
return son(tree[p].fa,1)==p;
}
inline bool root_check(int p){
return son(tree[p].fa,1)!=p&&son(tree[p].fa,0)!=p;
}
void rotate(int p){
int f=tree[p].fa,g=tree[f].fa,k=son_check(p);
!root_check(f)&&(son(g,son_check(f))=p),tree[p].fa=g;
son(f,k)=son(p,k^1),tree[son(p,k^1)].fa=f;
son(p,k^1)=f,tree[f].fa=p;
upd(f),upd(p);
}
void splay(int p){
int u=p;
while(!root_check(p)){
int f=tree[p].fa;
if(!root_check(f)) rotate(son_check(p)==son_check(f)?f:p);
rotate(p);
}
}
//Link-Cut-tree part
inline void smodify(int p,int s,int x){
tree[p].size+=x*tree[s].sum;
tree[p].de+=x*tree[s].sum*tree[s].sum;
tree[p].ad+=x*tree[s].ans;
//p的虚子树多了（少了）s，sum->size sum^2->de ans->ad
}
inline void access(int p){
for(int x=0;p;p=tree[x=p].fa) splay(p),smodify(p,son(p,1),1),son(p,1)=x,smodify(p,son(p,1),-1),upd(p);
}
inline void link(int x,int y){
access(y);splay(y);
access(x);splay(x);
tree[y].fa=x;
smodify(x,y,1);upd(x);
}
inline void cut(int x,int y){
access(x);splay(x);splay(y);
tree[y].fa=0;
smodify(x,y,-1);upd(x);
}
inline bool ancesstor(int x,int y){
access(y);splay(y);splay(x);
if(root_check(y)) return false;
return true;
}
int fa[N];
int main(){
scanf("%d",&n);
rep(i,2,n) scanf("%d",&fa[i]);
rep(i,1,n){
scanf("%d",&a[i]);
tree[i].all=tree[i].ans=a[i];
tree[i].sum=tree[i].size=1;
}
rep(i,2,n) link(fa[i],i);
access(1);splay(1);
int _; long double __=1LL*n*n,Ans=tree[1].ans/__;
printf("%0.13Lf\n",Ans);
scanf("%d",&_);
while(_--){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==1){
if(!ancesstor(x,y)){
cut(fa[x],x);link(y,x);
fa[x]=y;
}else{
cut(fa[y],y);link(x,y);
fa[y]=x;
}
access(1);splay(1);
Ans=tree[1].ans/__;
}else{
access(x);splay(x);
a[x]=y;upd(x);
Ans=tree[x].ans/__;
}
printf("%0.13Lf\n",Ans);
}
return 0;
}