P7246 手势密码 解题报告

解题报告

P7246 手势密码解题报告：

更好的阅读体验

题意

• 给定一颗$n$个点带点权的树，可以用若干条简单路径覆盖树，使得每个点被覆盖的次数为它的点权。
• 数据范围：$1\leqslant n\leqslant 3\times 10^6$。

分析

非常神仙的贪心题。

考虑使用一种“帮忙”思想：对于以$x$为根的子树，我们将内部的点全部按要求覆盖，并从$x$延伸出$v_x$条路径来帮忙覆盖祖宗结点（某些路径也可以在$x$结点止步）。

因此我们做一遍树形dp，对于每个结点$x$，我们计算仅当前位置对答案的贡献，也就是说如果这里向上延伸出$1$条路径，那么贡献就加$1$；如果有两条路径在这里交汇或者一条路径在这里结束，那么贡献就减$1$（本来要两条路径，现在用一条路径就可以覆盖了）。

设$x$所有儿子组成了$son(x)$集合，那么很容易发现：

• 对于每一个$y,z\in son(x)$，$y$的路径可以和$z$的路径在$x$上连接起来（下文称之为匹配），这样就可以让$y$和$z$的两个操作变成一个操作，并可以让$x$多一次覆盖。
• 对于所有的儿子，两两之间匹配最多匹配$\lfloor\frac{sum}{2}\rfloor$次。
• 对于某个儿子$y$，满足$v_y=maxx$，那么我们发现如果其他的儿子都与$y$匹配（不考虑$y$不够的情况），那么最少也需要$sum-maxx$次匹配。

因此，在$x$结点上理论上可以进行$l=\min\{\lfloor\frac{sum}{2}\rfloor,sum-maxx\}$次匹配。

我们发现，在不增加$x$子树内对答案的贡献的情况下且不让$x$的覆盖次数超限的情况下，我们要减小匹配次数。因为我们减小匹配次数就可以让可以延伸出去的路径数更多，根据贪心的思想这样一定是更优的。

这里有一个问题，为什么要保证不增加$x$子树内对答案的贡献呢？延伸出去不是可以减小祖先对答案的贡献吗？

我们发现对于某一条路径，且当前子树的根的覆盖次数还没有满，那么如果它在这里匹配，那么会减小$1$的贡献；而如果延伸出去，只是有可能减小$1$的贡献（有可能匹配不到路径）。因此我们发现在当前子树能减小贡献我们直接匹配一定是不劣的。

我们设当前根结点为$x$，在$x$处的匹配次数为$y$，那么有$y+(sum-2y)=a_x$（$y$条在$x$处匹配的路径，其余的路径都向上延伸，共$sum-2y$条），也就是$y=sum-a_x$。

那么，我们当前子树最优匹配次数为$match=\min\{l,a_x,sum-a_x\}$。

知道了子树最优匹配次数，那么其他的都好算了。

$v_x=a_x-match$（显然除去匹配的路径数对$x$的覆盖数量，其余$a_x$的每次覆盖都可以帮祖宗的忙）

而$x$结点对答案的贡献为$\max\{a_x-(sum-match),0\}-match$（所有路径能覆盖的次数为$(sum-2match)+match=sum-match$，因此$x$结点还需要$a_x-(sum-match)$次覆盖）。

时间复杂度：$O(n)$。

代码

#include<stdio.h>
#define int long long
const int mod=1000000000,maxn=3000005,maxm=maxn<<1;
int op,n,seed,e,ans;
int a[maxn],start[maxn],to[maxm],then[maxm],v[maxn];
inline int getseed(int x){
    seed=(1ll*seed*0x66CCF+19260817ll)%x+1;
    seed=(1ll*seed*0x77CCF+20060428ll)%x+1;
    seed=(1ll*seed*0x88CCF+12345678ll)%x+1;
    seed=(1ll*seed*0x33CCCCFF+10086001ll)%x+1;
    return seed;
}
inline int max(int a,int b){
    return a>b? a:b;
}
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    int sum=0,maxx=0,match;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x),sum+=v[y],maxx=max(maxx,v[y]);
    }
    match=max(0,min(min(sum/2,sum-maxx),min(a[x],sum-a[x])));
    v[x]=a[x]-match;
    ans+=max(a[x]-(sum-match),0)-match;
}
signed main(){
    scanf("%lld",&op);
    if(op==1){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%lld%lld",&x,&y);
            add(x,y),add(y,x);
        }
    }
    if(op==2){
        scanf("%lld%lld",&seed,&n);
        for(int i=1;i<=n;i++)
            a[i]=getseed(mod);
        for(int i=2;i<=n;i++){
            int x=getseed(i-1);
            add(x,i),add(i,x);
        }
    }
    dfs(1,0);
    printf("%lld\n",ans);
    return 0;
}