神题。
考虑刻画题目中的条件，树是 “美丽的” 等价于未点亮的点形成的连通块数 \(=1\)，树上容易转化为 未点亮点数 - 两端点均未点亮边数。而计数点亮连通块数也一样可以转化，但还有一种方式是将每一棵点亮子树的贡献视为其根到父亲的连边，也就是两端点异色的边数。
对每个时间计数，这个数据范围必定是要以时间维维护数据结构。
考虑加减边的影响。对于边 \((u,v),t_u<t_v\)，其中 \(t_i\) 为点 \(i\) 点亮的时间。则等价于 \([1,t_u)\) 对两边均未点亮的边数贡献 \(1\)，\([t_u,t_v)\) 对两端点异色的边数贡献 \(1\)。特别的，\(t_1=n\)。
而所有时刻权值和相当于所有全局最小值时间对应的权值之和。（最小值即最小未点亮连通块数，权值即异色边数）。
断边则反贡献一遍即可。
Takanashi Rikka
// Problem: P8990 [北大集训 2021] 小明的树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8990
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=5e5+5;
int n,m,p[N],u[N],v[N];
struct node{int l,r,mn,c,x,laz,lazt;}t[N<<2];
void build(int u,int l,int r){t[u]={l,r,n-l,1,0,0,0};if(l==r)return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
inline void MIN(int u,int x){t[u].mn+=x,t[u].lazt+=x;}
inline void add(int u,int x){t[u].x+=x*t[u].c,t[u].laz+=x;}
inline void pd(int u){add(u<<1,t[u].laz),add(u<<1|1,t[u].laz),t[u].laz=0;MIN(u<<1,t[u].lazt),MIN(u<<1|1,t[u].lazt),t[u].lazt=0;
}
inline void pushup(int u){t[u].mn=min(t[u<<1].mn,t[u<<1|1].mn);bool x=(t[u<<1].mn==t[u].mn),y=(t[u<<1|1].mn==t[u].mn);t[u].c=x*t[u<<1].c+y*t[u<<1|1].c,t[u].x=x*t[u<<1].x+y*t[u<<1|1].x;
}
void upd(int u,int l,int r,int x){if(l>r)return;if(t[u].l>=l&&t[u].r<=r)return add(u,x);int mid=t[u].l+t[u].r>>1;pd(u);if(l<=mid)upd(u<<1,l,r,x);if(r>mid)upd(u<<1|1,l,r,x);pushup(u);
}
void update(int u,int l,int r,int x){if(l>r)return;if(t[u].l>=l&&t[u].r<=r)return MIN(u,x);int mid=t[u].l+t[u].r>>1;pd(u);if(l<=mid)update(u<<1,l,r,x);if(r>mid)update(u<<1|1,l,r,x);pushup(u);
}
void ins(int u,int v){int x=p[u],y=p[v];if(x>y)swap(x,y);update(1,1,x-1,-1),upd(1,x,y-1,1);
}
void del(int u,int v){int x=p[u],y=p[v];if(x>y)swap(x,y);update(1,1,x-1,1),upd(1,x,y-1,-1);
}
void UesugiErii(){cin>>n>>m;for(int i=1;i<n;i++)cin>>u[i]>>v[i];for(int i=1,x;i<n;i++)cin>>x,p[x]=i;p[1]=n;build(1,1,n-1);for(int i=1;i<n;i++)ins(u[i],v[i]);cout<<t[1].x<<'\n';while(m--){int x,y,u,v;cin>>x>>y>>u>>v;del(x,y),ins(u,v);cout<<t[1].x<<'\n';}
}
signed main(){cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}