P12205 solution

4C45 · 2026-05-13 22:05:43 · 题解

喵喵线喵。

在若干子树内添加区间限制并在点上求并，考虑拿 DFS 序把树拍成一条链，子树限制变成连续区间，限制变为给定若干矩形，在某条纵轴上求经过的矩阵并中的整点数，然后就是扫描线板子了。

注意开大空间。

:::info[P12205]

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ir(i,a,b) for(int i=b;i>=a;i--)
#define db double
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define re return
#define len(str) (str.length())
#define inr(L,R,l,r) (l<=L and R<=r)
#define ofr(L,R,l,r) (L>r or l>R)
#define lowbit(x) (x&(-x))
#define tn2 tuple<node*,node*>
#define tn3 tuple<node*,node*,node*>
#define mt make_tuple
#define np nullptr
#define ioo cin.tie(0)->sync_with_stdio(0);cout.tie(0)->sync_with_stdio(0);
#define popc __builtin_popcount
using namespace std;
int n,m;
const int maxn=1e6+114;
ll head[maxn],to[2*maxn],nxt[2*maxn],vb[maxn*2],vt[maxn*2],pl[maxn],pr[maxn],dfn[maxn],siz[maxn],ts,idfn[maxn],ans[maxn];
ll sl[maxn*4],sr[maxn*4];
int cnt=0;
void add(int u,int v,int l,int r)
{
    ++cnt;
    nxt[cnt]=head[u];head[u]=cnt;
    to[cnt]=v;vb[cnt]=l;vt[cnt]=r;
}
void dfs(int u,int fa)
{
    siz[u]=1;
    ts++;
    dfn[u]=ts;idfn[ts]=u;
    for(int i=head[u];i;i=nxt[i])
    {
        int v,l,r;
        v=to[i];
        l=vb[i];
        r=vt[i];
        if(fa==v) continue;
        dfs(v,u);
        pl[v]=l;
        pr[v]=r;
        siz[u]+=siz[v];
    }
}
struct node
{
    ll w,cov,len;
} t[maxn<<2];
void build(int u,int L,int R)
{
    if(L==R )
    {
        t[u].len=sr[L]-sl[L]+1;
    }else{
        int M=L+R>>1;
        build(2*u,L,M);
        build(2*u+1,M+1,R);
        t[u].len=sr[R]-sl[L]+1;
    }
}
void fix(int u)
{
    if(t[u].cov) t[u].w=t[u].len;
    else t[u].w=t[2*u].w+t[2*u+1].w;
}
void update(int u,int L,int R,int l,int r,int v)
{
    if(inr(L,R,l,r))
    {
        t[u].cov+=v;
        fix(u);
    }else if(!ofr(L,R,l,r))
    {
        int M=L+R>>1;
        update(2*u,L,M,l,r,v);
        update(2*u+1,M+1,R,l,r,v);
        fix(u);
    }
}
ll query(int u,int L,int R,int l,int r)
{
    if(inr(L,R,l,r)) re t[u].w;
    else if(ofr(L,R,l,r)) re 0;
    else
    {
        int M=L+R>>1;
        re query(2*u,L,M,l,r)+query(2*u+1,M+1,R,l,r);
    }
}
struct modify
{
    int l,r,t,v;
    friend bool operator<(modify a,modify b)
    {
        re a.t<b.t;
    }
} q[maxn*2];
int main()
{
    cin>>n>>m;
    rep(i,1,n-1)
    {
        int a,b,L,R;
        cin>>a>>b>>L>>R;
        add(a,b,L,R);
        add(b,a,L,R);
    }
    rep(i,1,cnt) sl[i*2-1]=vb[i],sl[i*2]=vt[i];
    sort(sl+1,sl+cnt*2+1);
    int k=unique(sl+1,sl+cnt*2+1)-sl-1;
    int tk=k;
    rep(i,1,tk-1)
    {
        sr[i]=sl[i];
        if(sl[i]!=sl[i+1]-1)
        {
            sl[++k]=sl[i]+1;
            sr[k]=sl[i+1]-1; 
        }
    } 
    sr[tk]=sl[tk];
    sort(sl+1,sl+k+1);
    sort(sr+1,sr+k+1);
    rep(i,1,cnt) 
    {
        vb[i]=lower_bound(sl+1,sl+k+1,vb[i])-sl;
        vt[i]=lower_bound(sr+1,sr+k+1,vt[i])-sr;
    }
    dfs(1,0);build(1,1,k);
    int tot=0;
    rep(i,2,n)
    {
        q[++tot].l=pl[i];
        q[tot].r=pr[i];
        q[tot].t=dfn[i];
        q[tot].v=1;
        q[++tot].l=pl[i];
        q[tot].r=pr[i];
        q[tot].t=dfn[i]+siz[i];
        q[tot].v=-1;
    }
    sort(q+1,q+tot+1);
    int j=1;
    rep(i,2,n)
    {
        while(j<=tot and q[j].t==i) update(1,1,k,q[j].l,q[j].r,q[j].v),j++;
        ans[idfn[i]]=t[1].w;
    }
    rep(i,2,n) cout<<ans[i]<<endl;
}

:::