浅谈卡时
hgckythgcfhk · · 题解
前言
首先，这是蒟蒻的第一篇题解（当然，那篇乱搞被打回的不算），然后，如果你想学树上 dp + 容斥的正解，请跳过此题解。
建图
关于建图，其他题解也说的很明白了，边权等于删掉这条边所产生的两个联通快的节点个数的乘积，但我的做法中，还会给每个点赋上该点的所有边的边权之和的点权。
核心部分
按点权排序，与其他题解的按边排序不同，按点权排序的正确性更有保证，考虑如果存在一个点的点权不是最大，该点作为答案的概率非常小，即使是答案，也一定离点权最大的点很近，因为边权是平方级的，所以边权的差会很大，导致点权的差很大，由于点权等于边权的和，对于随机的数据来说，点权的差也基本大于等于平方级，如果不选最大的点，至少在这个点上会减少平方级的贡献，考虑到可能会有点权相等的点，所以要对所有点权最大的点遍历，但点不会太多，可以用反证法证明这样的点要么是重心，要么与重心相邻，证明比较复杂，但这个结论是显然的，也就是说，我们可以只判断
关于按边权排序，显然也是正确的，但是我们习惯处理点，并不习惯处理边，而且用 vector 存图的话还需要额外开一个结构体，对于链式前向星，本身就很不方便，主要是我不会。
这里介绍一个很简单但不容易想到的小技巧，sort 的 cmp 函数不仅可以重载结构体的排序，也可以实现直接从大到小排序，比较方式可以是比较数组中以这两个元素为下标的值，这很好理解，因为这就是基础的语法，但第一次见不一定能想到。
这个做法虽然是乱搞但正确性和时间复杂度有保证，起码在本题数据范围和稍微大一点的范围下构造不出卡掉这个做法的数据，即使可以，随机交换几个元素的枚举顺序，或者随机在点权上加上一个不大的扰动值，可以以几乎可以忽略不计的出错率卡过所有数据，而且，想卡这个做法，必须人工构造数据，但这不好构造，比如对于本题数据，卡到
而且越大的数据，不是最大点权的概率越小，对于
程序如下
#include<bits/stdc++.h>
using namespace std;
#define void inline void
#define int register unsigned short
#define ll unsigned long long
#define rr register ll
const unsigned short N=30001;vector<unsigned short>a[N];vector<ll>w[N];
ll dp[N];unsigned short s[N],f[N],k,n;bitset<N>b;
void dfs(int u){s[u]=1;for(int i=0;i<a[u].size();++i){int v=a[u][i];
if(v==f[u])continue;f[v]=u;dfs(v);s[u]+=s[v];}}unsigned short d[N];
inline ll bfs(int u){rr ans=0;static unsigned short q[N<<1],l,r;q[0]=u;b[u]=1,l=r=0;
d[u]=0;while(l<=r){int t=q[l++];for(int i=0;i<a[t].size();++i){int v=a[t][i];
if(b[v])continue;ans+=w[t][i];if(d[t]>=k)continue;q[++r]=v;b[v]=1;d[v]=d[t]+1;}}
b.reset(),memset(d,0,sizeof d);return ans;}
#define add(u,v) a[u].emplace_back(v);a[v].emplace_back(u)
void dpdate(int u){for(int i=0;i<a[u].size();++i){int v=a[u][i];
if(v==f[u]){w[u].emplace_back(s[u]*(n-s[u]));continue;}
w[u].emplace_back(s[v]*(n-s[v]));dpdate(v);}}
inline ll max(ll a,ll b){return a>b?a:b;}unsigned short id[N];
inline bool cmp(const int &a,const int &b){return dp[a]<dp[b];}
signed main(){ios::sync_with_stdio(0);unsigned t=clock();
cin>>n>>k;for(int i=n-1;i;--i){int u,v;cin>>u>>v;add(u,v);}dfs(1);ll ans=0;
dpdate(1);for(int i=n,j;i;--i){dp[i]=n-s[i];for(j=0;j<a[i].size();++j)dp[i]+=w[i][j];}
for(int i=1;i<=n;++i)id[i]=i;sort(id+1,id+n+1,cmp);
for(int i=n;i;--i){ans=max(ans,bfs(id[i]));if(clock()-t>500)break;}cout<<ans;}如果你愿意写快读，完全能把最优解抢走，但