NC21165. 死宅选点
描述
输入描述
一行两个数n,k
接下来n-1行，每行2个数u,v表示存在一条从u到v的边.
输出描述
一行一个整数表示使厌恶度之和最小的点, 若有多个点厌恶度之和相同. 输出编号最小的一个.
示例1
输入:
4 2 1 2 2 3 2 4
输出:
2
说明:
2号点到1, 3, 4点的路径的厌恶度都是2，厌恶度总和为 6C++14(g++5.4) 解法, 执行用时: 194ms, 内存消耗: 88544K, 提交时间: 2019-04-19 16:11:34
#include <bits/stdc++.h>
using namespace std;
const int N=20010;
const int L=550;
int dp[N][L+10],ans[N][L+10],tmp[L+10],n,k;
vector<int> v[N];
void dfs1(int x,int f)
{
int son;
for(int i=0;i<v[x].size();i++){
son=v[x][i];
if(son==f)
continue;
dfs1(son,x);
}
for(int d=1;d<=L;d++)
for(int i=0;i<v[x].size();i++){
son=v[x][i];
if(son==f)
continue;
dp[x][d]+=dp[son][d-1];
if(k>1&&dp[x][d]>=k){
dp[x][d+1]++;
dp[x][d]-=k;
}
}
}
void dfs2(int x,int f)
{
int son,lazy;
for(int i=0;i<v[x].size();i++){
son=v[x][i];
if(son==f)
continue;
lazy=0;
tmp[0]=1;
for(int d=1;d<=L;d++){
tmp[d]=ans[x][d]-dp[son][d-1]-lazy;
if(k>0&&tmp[d]<0){
tmp[d]+=k;
lazy=1;
}
else
lazy=0;
}
for(int d=1;d<=L;d++){
ans[son][d]+=tmp[d-1]+dp[son][d];
if(k>1&&ans[son][d]>=k){
ans[son][d+1]++;
ans[son][d]-=k;
}
}
dfs2(son,x);
}
}
bool cmp(int x,int y){
int sum1,sum2;
if(k==1){
sum1=0,sum2=0;
for(int i=1;i<L;i++){
sum1+=ans[x][i]*i;
sum2+=ans[y][i]*i;
}
return sum1<sum2;
}
else{
for(int i=L-1;i>=1;i--){
if(ans[x][i]!=ans[y][i])
return ans[x][i]<ans[y][i];
}
return 0;
}
}
int main()
{
scanf("%d%d",&n,&k);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++)
dp[i][0]=1;
dfs1(1,-1);
for(int i=0;i<L;i++)
ans[1][i]=dp[1][i];
dfs2(1,-1);
x=1;
for(int i=2;i<=n;i++)
if(cmp(i,x))
x=i;
printf("%d\n",x);
}
C++11(clang++ 3.9) 解法, 执行用时: 216ms, 内存消耗: 79196K, 提交时间: 2019-10-03 15:08:43
#include<bits/stdc++.h>
using namespace std;
const int M=20001,P=100000000;
int n,k,a,b;
int head[M],to[M<<1],nxt[M<<1],tot;
void Link(int a,int b){
nxt[++tot]=head[a];
to[tot]=b;
head[a]=tot;
}
int dp[M][505],sh[M][505];
void dfs(int x,int la){
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==la)continue;
dfs(y,x);
for(int j=1;j<=500;j++)dp[x][j]+=dp[y][j-1];
}
dp[x][0]=1;
}
void DFS(int x,int la){
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==la)continue;
for(int j=2;j<=500;j++)sh[y][j]=dp[x][j-1]+sh[x][j-1]-dp[y][j-2];
sh[y][1]=dp[x][0]+sh[x][0];
sh[y][0]=1;
DFS(y,x);
}
}
int ans;
void Solve_100(){
dfs(1,0),DFS(1,0);
for(int i=1;i<=n;i++){
for(int j=500;j>=1;j--){
dp[i][j]+=sh[i][j];
dp[i][j]+=dp[i][j+1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=500;j++){
dp[i][j+1]+=dp[i][j]/k;
dp[i][j]%=k;
}
}
ans=1;
for(int i=2;i<=n;i++){
for(int j=501;j>=1;j--){
if(dp[i][j]<dp[ans][j]){
ans=i;
break;
}
if(dp[ans][j]<dp[i][j])break;
}
}
printf("%d\n",ans);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
Link(a,b),Link(b,a);
}
Solve_100();
}