P3554 [POI2013]LUK-Triumphal arch

2018-09-09 21:40:40


因为所求的值类似于一个覆盖范围,所以无法直接求解

用二分转化为判定性问题

然后就是树形 $dp$ 了

可以看出B一定只会从根节点走到叶子结点,不会走回头路

(走回头路相当于自己啥也没干还让A多染了几次色)

设 $f[i]$ 表示在 $i$ 的子树中(不包括 $i$ )还需要染色的次数

转移就是求出 $i$ 的子节点的 $f$ 值总和,记为 $sum$

然后 $f[i]=max(0,sum+d[i]-mid)$

$d[i]$ 表示 $i$ 的度数(不包括它的父节点)

每一次二分都做一次dp

如果 $f[1]==0$ ,则答案可行

关于数据范围:bzoj是3e5,luogu没给,但是1e5可以过

我先在luogu做的交到bzoj还RE了一发

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=3e5+5;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,num,head[N],f[N],mid;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k,int fa)
{
    int sum=0;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue;
        dfs(v,k); sum+=f[v]+1;
    }
    f[k]=max(sum-mid,0);
}
int main()
{
    n=read();
    if (n==1) {puts("0"); return 0;}
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    int l=1,r=n-1,ans=0;
    while (l<=r)
    {
        memset(f,0,sizeof(f));
        mid=(l+r)>>1; dfs(1,0);
        if (!f[1]) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}