求帮卡常
查看原帖
求帮卡常
787229
kdx_dy楼主2024/8/6 10:40

RT

#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=3e5+5,P=1e9+7;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int wtp,wstk[40];
void write(int x,char c=0){
    if(x<0) putchar('-'),x=-x;
    do{
        wstk[++wtp]=x%10,x/=10;
    }while(x);
    while(wtp) putchar(wstk[wtp--]^48);
    if(c) putchar(c);
}
int n,C,all=1,sum,ans,l[N],r[N],len[N],inv[N];vector<int>E[N];vector<pii>vec[N];
void add(int &x,int y){x+=y;if(x>=P) x-=P;}
void del(int &x,int y){x-=y;if(x<0) x+=P;}
int qpow(int x,int y){int res=1;for(;y;y>>=1){if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}return res;}
int rt,tot,cnt,sz[N],mx[N],vis[N],fa[N];unordered_map<int,int>dep[N],bl[N];
void getrt(int u,int f){
	sz[u]=mx[u]=1;
	for(int v:E[u]) if(v!=f&&!vis[v]) getrt(v,u),sz[u]+=sz[v],mx[u]=max(mx[u],sz[v]);
	mx[u]=max(mx[u],tot-sz[u]);
	if(mx[rt]>mx[u]) rt=u;
}
void dfs(int u,int f,int id){
	dep[id][u]=dep[id][f]+1,bl[id][u]=cnt;
	for(int v:E[u]) if(v!=f&&!vis[v]) dfs(v,u,id);
}
void solve(int u){
	vis[u]=1;
	for(int v:E[u]) if(!vis[v]) cnt++,dfs(v,u,u);
	int tmp=tot;
	for(int v:E[u]) if(!vis[v]){
		tot=sz[v]>sz[u]?tmp-sz[u]:sz[v];
		mx[rt=0]=N,getrt(v,u),fa[rt]=u,solve(rt);
	}
}
int dp1[N],dp2[N];
void Insert(int x){
	int id=x;
	while(id){
		int p=bl[id][x];
		add(sum,1ll*dep[id][x]*inv[x]%P*all%P*dp1[id]%P),add(sum,1ll*all*inv[x]%P*dp2[id]%P);
		if(id!=x) del(sum,1ll*dep[id][x]*inv[x]%P*all%P*dp1[p]%P),del(sum,1ll*all*inv[x]%P*dp2[p]%P);
		add(dp1[id],inv[x]),add(dp2[id],1ll*dep[id][x]*inv[x]%P);
		if(id!=x) add(dp1[p],inv[x]),add(dp2[p],1ll*dep[id][x]*inv[x]%P);
		id=fa[id];
	}
}
void Delete(int x){
	int id=x;
	while(id){
		int p=bl[id][x];
		del(dp1[id],inv[x]),del(dp2[id],1ll*dep[id][x]*inv[x]%P);
		if(id!=x) del(dp1[p],inv[x]),del(dp2[p],1ll*dep[id][x]*inv[x]%P);
		del(sum,1ll*dep[id][x]*inv[x]%P*all%P*dp1[id]%P),del(sum,1ll*all*inv[x]%P*dp2[id]%P);
		if(id!=x) add(sum,1ll*dep[id][x]*inv[x]%P*all%P*dp1[p]%P),add(sum,1ll*all*inv[x]%P*dp2[p]%P);
		id=fa[id];
	}
}
int main(){
	n=cnt=read();
	for(int i=1;i<=n;i++){
		l[i]=read(),r[i]=read(),C=max(C,r[i]),len[i]=r[i]-l[i]+1,all=1ll*all*len[i]%P,inv[i]=qpow(len[i],P-2);
		vec[l[i]].push_back(mp(i,1)),vec[r[i]+1].push_back(mp(i,-1));
	}
	for(int i=1,u,v;i<n;i++) u=read(),v=read(),E[u].push_back(v),E[v].push_back(u);
	mx[rt=0]=N,tot=n,getrt(1,0),solve(rt);
	for(int i=1;i<=C;i++){
		for(pii now:vec[i]) (now.se==1)?Insert(now.fi):Delete(now.fi);
		add(ans,sum);
	}
	write(ans,'\n');
	return 0;
}

2024/8/6 10:40
加载中...