【0】做题心得 - 2025 NOIP #66 - T1【计数】【点边容斥】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
const ll P=1e9+7;
int n;
ll lx,rx,ly,ry,x[N],y[N];
int fat[N];
ll ans;
vector<int>e[N];
void dfs(int p,int fa){
	fat[p]=fa;
	for(auto v:e[p])if(v^fa)
		dfs(v,p);
	return;
}
int main(){
	freopen("build.in","r",stdin);
	freopen("build.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>lx>>rx>>ly>>ry;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	x[0]=-1,y[0]=-1;
	for(int i=1;i<=n;i++){
		ll posx=x[i],posy=y[i];
		ll fatx=x[fat[i]],faty=y[fat[i]];
		ans+=(posx-lx+1ll)%P*(rx-posx+1ll)%P*(posy-ly+1ll)%P*(ry-posy+1ll)%P;
		ans%=P;
		if(fatx!=-1){
			ll elx=min(posx,fatx), ely=min(posy,faty),
			   erx=max(posx,fatx), ery=max(posy,faty);
			ans-=(elx-lx+1ll)%P*(rx-erx+1ll)%P*(ely-ly+1ll)%P*(ry-ery+1ll)%P;
			ans=(ans+P)%P;
		}
	}
	cout<<ans;
	return 0;
}