题解 P5628 【【AFOI-19】面基】

· · 题解

这道题目是那天打比赛时想骗更多的分但想不到正解

眼看着就要吃晚饭了，马上飞去小店买面包吃回来时想出的乱搞做法

大致题意

给你一棵树，每条边有一个重要度：若一条道路无法使用，会导致有 t对路口无法相互抵达，则t就是该道路的重要度。

施工会使以某一个点的周围与之距离不超过k的点被删，从而与之连的边被删，求被删的边的重要度和的最大值

正解是树上容斥然而我这么菜怎么会想到正解

而我介绍的方法是玄学乱搞

思路：

对于处理边权（重要度），我们dfs搜一遍，边权就是以该边左端点为根的子树大小乘上剩下端点数

具体处理方法(size[i]表示以i为根的子树大小,in[k]表示第k条边的重要度)

inline void dfs(int x,int father)
{
    size[x]=1;
    for(int k=First[x];k;k=Next[k])
    {
        if(to[k]==father) continue;
        dfs(to[k],x);
        size[x]+=size[to[k]];
        in[k]=size[to[k]]*(n-size[to[k]]);
    }
}

那么处理好了边权，我们这么找出施工中的那个点呢？

相信大家都能想到朴素算法，对于每一个点搜索并记录，

但是如果是链的话，时间复杂度k n，而菊花图则会被卡到n n，

显然容易超时,这时我们怎么办呢？

下面开始胡说讲解重点

(注:这种想法十分不严谨，但不失为骗分好方法)

我们需要考虑选择什么样的点作为起点更有可能使得结果最大

这时候想到重要度的定义，如果一条边重要度大的话，那么被这条边分开的两个连通块的点数的乘积就会多

我们可以不严谨地认为，在重要度大的边附近的边重要度大的概率大

相反，在比较边界的地方，重要度小的边附近的边重要的小的概率大

那么，我们就考虑记录每个点连接的边的重要度之和，并按此排序

先从我们认为最优的开始搜索

在搜索得快时间超限的时候把他打断，输出此时的答案即可满分

（我自己比赛时在dfs最里层加了一个计数的变量,当他大于10000000时打断最后还跑得挺快）

上代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=3e4+5;
#define int long long 
int ans,number;
inline int R()
{
    char c;int sign=1,res=0;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;
    res+=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    return res*sign;
}//读入优化 
int First[Maxn],Next[Maxn*2],to[Maxn*2],cnt,n,K;
int in[Maxn*2],size[Maxn];
struct Point
{
    int we,id;
}a[Maxn];//记录每个点连结的边的重要度和其编号 
bool cmp(Point x,Point y)
{
    return x.we>y.we;
}
inline void add(int z,int y)
{
    Next[++cnt]=First[z];
    First[z]=cnt;
    to[cnt]=y;//加边 
}
inline void dfs(int x,int father)//第一边预处理的dfs 
{
    size[x]=1;
    for(int k=First[x];k;k=Next[k])
    {
        if(to[k]==father) continue;
        dfs(to[k],x);
        size[x]+=size[to[k]];//记录子树大小 
        in[k]=size[to[k]]*(n-size[to[k]]);//计算边的重要度 
        a[x].we+=in[k];//统计点的权值（连出去的边的重要度和） 
        a[to[k]].we+=in[k];
    }
}
int now;
inline void dfs2(int x,int father,int num)
{//x为该节点，father为其父亲,num为其到最初点的距离 
    if(num>K) return;
    number++;//计数 
    for(int k=First[x];k;k=Next[k])
    {
        if(to[k]==father) continue;
        now+=in[k];//统计重要度 
        dfs2(to[k],x,num+1);
    }
    return;
}
signed main()
{
    n=R();K=R();int x,y;
    for(int i=1;i<=n;i++) a[i].id=i;
    for(int i=1;i<n;i++)
    {
        x=R();y=R();
        add(x,y);add(y,x);
    }//加边 
    dfs(1,0);//预处理 
    for(int i=1;i<=cnt;i+=2) 
    in[i]=in[i+1]=max(in[i],in[i+1]);
    //第2i-1条与第2i为同一条边，只是方向不同 
    sort(a+1,a+1+n,cmp);//按权值排序 
    for(int i=1;i<=n;i++)
    {
        now=0;
        if(number>10000000) break;//及时退出，防止tle 
        dfs2(a[i].id,0,0);//记录答案 
        if(now>ans) ans=now;//更新答案 
    }
    printf("%lld\n",ans);
}

觉得好别忘点个赞再走qwq