NOIP 模拟 $33; m Defence$

题解 (by;zjvarphi)

题意就是维护 ( m max{01mx,01l+01r}) 就是最长连续的一段 (0)，左右 (0) 区间的加和。

可以启发式合并，也可以直接线段树合并，复杂度 (mathcal O m(nlogn))

Code:

#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
namespace IO{
    char buf[1<<21],*p1=buf,*p2=buf;
    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
    struct nanfeng_stream{
        template<typename T>inline nanfeng_stream &operator>>(T &x) {
            ri f=0;x=0;register char ch=gc();
            while(!isdigit(ch)) f|=ch=='-',ch=gc();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
            return x=f?-x:x,*this;
        }
    }cin;
}
using IO::cin;
namespace nanfeng{
    #define FI FILE *IN
    #define FO FILE *OUT
    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
    static const int N=1e5+7;
    struct edge{int v,nxt;}e[N];
    int first[N],ans[N],t=1,n,m,q;
    inline void add(int u,int v) {e[t].v=v,e[t].nxt=first[u],first[u]=t++;}
    struct Seg{
        #define ls(x) T[x].lt
        #define rs(x) T[x].rt
        struct segmenttree{int siz,l,r,lt,rt,mx;}T[N<<6];
        int rt[N],tot;
        inline void up(int x) {
            int l=ls(x),r=rs(x);
            T[x].siz=T[l].siz+T[r].siz;
            T[x].mx=cmax(T[l].mx,T[r].mx);
            if (T[l].r&&T[r].l) T[x].mx=cmax(T[x].mx,T[r].l-T[l].r-1);
            if (T[l].l) T[x].l=T[l].l;else T[x].l=T[r].l;
            if (T[r].r) T[x].r=T[r].r;else T[x].r=T[l].r;
        }
        void update(int &x,int p,int l,int r) {
            if (!x) x=p(tot);
            if (l==r) {
                T[x].l=T[x].r=l;
                T[x].siz=1;
                return;
            }
            int mid(l+r>>1);
            if (p<=mid) update(ls(x),p,l,mid);
            else update(rs(x),p,mid+1,r);
            up(x);
        }
        int merge(int x,int y,int l,int r) {
            if (!x||!y) return x|y;
            if (l==r) return x;
            int mid(l+r>>1);
            ls(x)=merge(ls(x),ls(y),l,mid);
            rs(x)=merge(rs(x),rs(y),mid+1,r);
            up(x);
            return x;
        }
    }T;
    void dfs(int x) {
        for (ri i(first[x]),v;i;i=e[i].nxt) {
            dfs(v=e[i].v);
            T.rt[x]=T.merge(T.rt[x],T.rt[v],1,m);
        }
        ans[x]=T.T[T.rt[x]].siz?T.T[T.rt[x]].mx:-1;
        if (ans[x]!=-1) ans[x]=cmax(ans[x],T.T[T.rt[x]].l-1+m-T.T[T.rt[x]].r);
    }
    inline int main() {
        //FI=freopen("nanfeng.in","r",stdin);
        //FO=freopen("nanfeng.out","w",stdout);
        cin >> n >> m >> q;
        for (ri i(1),u,v;i<n;p(i)) cin >> u >> v,add(u,v);
        for (ri i(1),u,p;i<=q;p(i)) cin >> u >> p,T.update(T.rt[u],p,1,m);
        dfs(1);
        for (ri i(1);i<=n;p(i)) printf("%d
",ans[i]);
        return 0;
    }
}
int main() {return nanfeng::main();}