【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;
}