正文
【CF1249F】Maximum Weight Subset(贪心)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
题意:给定一棵n个点带点权的树,要求从中选出一个点集,使得这些点两两之间距离都大于K,求最大点权和
n,K<=2e2,1<=a[i]<=1e5
思路:树形DP显然可做,极限是n方,然而贪心也是,还比dp好写
可以用寒假camp里cls差不多的想法
从深度大的向上贪心,暴力维护对答案的贡献,即如果贡献大于0就取,并将距当前点距离<=K的贡献减去当前点
评论区甚至有红名大佬做到了线性复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 300010
#define M 2000010
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int dx[]={-,,,};
int dy[]={,,-,}; int head[N],nxt[N],vet[N],a[N],b[N],d[N],dis[N],q[N],tot,n,K; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void add(int a,int b)
{
nxt[++tot]=head[a];
vet[tot]=b;
head[a]=tot;
} void dfs(int u,int fa)
{
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=fa)
{
d[v]=d[u]+;
dfs(v,u);
}
e=nxt[e];
}
} bool cmp(int a,int b)
{
return d[a]>d[b];
} int calc(int st)
{
rep(i,,n) dis[i]=-;
dis[st]=;
int t=,w=;
q[]=st;
int res=a[st];
while(t<w)
{
t++;
int u=q[t];
a[u]-=res;
if(dis[u]==K) continue;
int e=head[u];
while(e)
{
int v=vet[e];
if(dis[v]==-)
{
w++; q[w]=v; dis[v]=dis[u]+;
}
e=nxt[e];
} }
return res;
} int main()
{
n=read(),K=read();
rep(i,,n) a[i]=read();
rep(i,,n) head[i]=;
tot=;
rep(i,,n-)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs(,);
rep(i,,n) b[i]=i;
sort(b+,b+n+,cmp);
int ans=;
rep(i,,n)
if(a[b[i]]>) ans+=calc(b[i]);
printf("%d\n",ans);
return ;
}