传送门

成功打破四题定律!(四题定律:每做四题必有一题做不出来)

这题我竟然池沼地想了一个星期(虽然出去旅游也没怎么在想),中间想出了大量的错误做法,也写了很多版本的代码,这是坠痛苦的。。。差点就想弃题去看题解了, 不过为了打破封建迷信,最后还是把他做出来了。

这题我的想法就是对于每种染色方案$S=\{x|x\space is\space black\}$,必然对应着一个点集$ker(S)$,使得这个$ker(S)$中的每个点都能以某个半径(可以不同)染出$S$这种方案。根据观察与大胆猜测,每个可行的$S$对应的$ker(S)$要么是所有点,要么是一个孤立的点,要么是某个点做根时删掉一些子树后剩下的连通子树。讨论$ker(S)$显然比直接讨论$S$要简单,所以直接考虑$ker(S)$就行了。

显然第一种情况只有全染黑时才成立,第二种情况后面再说。考虑第三种情况,设根为$x$,把$x$的所有子树按最大深度排序,并设$x$的子树为$s_1,s_2,...,s_k$。首先删掉的子树一定是所有子树的一个后缀,即只能删掉$s_i,s_{i+1},...,s_k$。因为由于留下来的子树都必须染黑,并且$x\in ker(S)$,所以如果删掉一个子树并留下来另一个最大深度比他深的子树的话,这个删掉的子树肯定是要全部染黑的,这样的话这棵子树就也在$ker(S)$里面了,这就矛盾了。所以可以直接枚举删掉哪些子树,然后分别处理一下就行了(注意只删一个子树的时候要特判)。上面的第二种情况, 其实也等价于把所有子树都删了,一起处理就行了。

我的实现里面用了树状数组,而且对每个点的所有子树都排了序,所以复杂度是$O(n\log n)$。其实好像是可以$O(n)$做的。。。?我因为是在原来的1个log的错误算法基础上改的,所以就懒得改成$O(n)$了。。。(可以看到我的树状数组是全部修改完后再询问的。。。)

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

namespace Fenwick{
    int c[MAXN];

    void add(int x,int v){
        while(x<MAXN){
            c[x]+=v;
            x+=x&(-x);
        }
    }

    int sum(int x){
        int res=0;
        while(x){
            res+=c[x];
            x-=x&(-x);
        }
        return res;
    }
}

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume,deg[MAXN];
int pre[MAXN],w[MAXN][2],numw;
int d[MAXN],d2[MAXN];
char type[MAXN];
LL ans;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    w[x][0]=++numw;
    d[x]=0;
    pre[x]=p;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            d[x]=max(d[x],d[e[i].to]+1);
        }
    w[x][1]=numw;
}

void dfs2(int x,int p){
    pair<int,int> td1(-1,0),td2(-1,0);
    if(p) td1=make_pair(d2[x],0);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            pair<int,int> temp=make_pair(d[e[i].to],e[i].to);
            if(temp>td1) td2=td1,td1=temp;
            else if(temp>td2) td2=temp;
        }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            if(e[i].to==td1.second) d2[e[i].to]=td2.first+1;
            else d2[e[i].to]=td1.first+1;
            dfs2(e[i].to,x);
        }
}

void gao(int x){
    static pair<int,int> b[MAXN];
    int numb=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^pre[x])
            b[++numb]=make_pair(d[e[i].to]+1,Fenwick::sum(w[e[i].to][1])-Fenwick::sum(w[e[i].to][0]-1));
    if(pre[x])
        b[++numb]=make_pair(d2[x]+1,Fenwick::sum(n)-Fenwick::sum(w[x][1])+Fenwick::sum(w[x][0]-1));
    sort(b+1,b+numb+1);
    bool flag=(type[x]=='1');
    for(int i=0;i<numb;i++){
        if(b[i].second) flag=1;
        if(!flag) continue;
        if(i<numb-1) ans+=b[i+1].first-b[i].first;
        else{
            int t0=b[i].first;
            int t1=min(b[i+1].first-1,b[i].first+1);
            if(t0<=t1) ans+=t1-t0+1;
        }
    }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
        deg[u]++; deg[v]++;
    }
    scanf("%s",type+1);
    dfs(1,0);
    dfs2(1,0);
    ans++;
    for(int i=1;i<=n;i++) 
        if(type[i]=='1')
            Fenwick::add(w[i][0],1);
    for(int i=1;i<=n;i++) 
        gao(i);
    printf("%lld\n",ans);
    return 0;
}