A1575

A1575

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[101][101];
struct node{
	ll next,to,w;
}e[201];
ll home[101],w[101],siize[101];
ll n,q;
ll c;
void add(ll aa,ll bb,ll cc){
	e[++c].next=home[aa];
	e[c].to=bb;
	e[c].w=cc;
	home[aa]=c;
}
void dfs(ll h,ll fa){
//	cout<<h<<" "<<fa<<endl;
	dp[h][1]=w[h];
	siize[h]=1;
	ll ez[3],cnt=0;
	for(ll i=home[h];i;i=e[i].next){
		ll t=e[i].to;
		if(t==fa) continue;
		w[t]=e[i].w;
		dfs(t,h);
		ez[++cnt]=t;
		siize[h]+=siize[t];
	}
//	if(h==3) cout<<cnt<<endl;
	if(cnt==2){
		for(ll i=2;i<siize[h];i++){
			for(ll j=min(siize[ez[1]],i-1);j>=0;j--){
				ll k=i-j-1;
//				cout<<h<<" "<<i<<" "<<ez[1]<<" "<<j<<" "<<ez[2]<<" "<<k<<endl;
				if(k<0||k>siize[ez[2]]) continue;
//				cout<<h<<" "<<i<<" "<<ez[1]<<" "<<j<<" "<<ez[2]<<" "<<k<<endl;
				dp[h][i]=max(dp[h][i],dp[ez[1]][j]+dp[ez[2]][k]+w[h]);
			}
		}
		dp[h][siize[h]]=dp[ez[1]][siize[ez[1]]]+dp[ez[2]][siize[ez[2]]]+w[h];
	}
}
int main(){
	scanf("%lld %lld",&n,&q);
	for(ll i=1;i<n;i++){
		ll x,y,z;
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1,0);
//	for(ll i=1;i<=n;i++){
//		for(ll j=1;j<=n;j++) cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
	printf("%lld",dp[1][q+1]);
	return 0;
}

A1576

A1576

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll dp[105][105],s[105],w[105],home[105],cnt;
struct node{
	ll next,to;
}e[105];
void add(ll a,ll b){
	e[++cnt].next=home[a];
	e[cnt].to=b;
	home[a]=cnt;
}
void dfs(ll h,ll fa){
	dp[h][1]=w[h];
	s[h]=1;
	for(ll i=home[h];i;i=e[i].next){
		ll t=e[i].to;
		if(t==fa) continue;
		dfs(t,h);
		s[h]+=s[t];
			for(ll k=m+1;k>0;k--){
		for(ll j=1;j<=s[t]&&j<=k;j++){
				if(dp[h][k-j]){
					dp[h][k]=max(dp[h][k-j]+dp[t][j],dp[h][k]);
				}
		}
			}
	}
}
int main(){
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++){
		ll x,y;
		scanf("%lld %lld",&x,&y);
		add(x,i);
		w[i]=y;
	}
	w[0]=1;
	dfs(0,-1);
	printf("%lld",dp[0][m+1]-1);
	return 0;
}

A1577

A1577

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum[50001],n,d1[50001],d2[50001],ans;
void init(){
	for(ll i=1;i<=n;i++) for(ll j=2;j<=n/i;j++) sum[i*j]+=i;
}
void did(){
	for(ll i=n;i;i--){
		if(sum[i]<i){
			if(d1[i]+1>d1[sum[i]]){
				d2[sum[i]]=d1[sum[i]];
				d1[sum[i]]=d1[i]+1;
			}
			else if(d1[i]+1>d2[sum[i]]){
				d2[sum[i]]=d1[i]+1;
			}
		}
	}
}
int main(){
	scanf("%lld",&n);
	init();
	did();
	for(ll i=1;i<=n;i++){
		ans=max(ans,d1[i]+d2[i]);
	}
	printf("%lld",ans);
	return 0;
}

A1578

A1578

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,home[1501],dp[1501][2],cnt;
struct node{
	ll next,to;
}e[3001];
void add(ll a,ll b){
	e[++cnt].to=b;
	e[cnt].next=home[a];
	home[a]=cnt;
}
void dfs(ll h,ll fa){
	dp[h][0]=0;
	dp[h][1]=1;
	for(ll i=home[h];i;i=e[i].next){
		ll t=e[i].to;
		if(t==fa) continue;
		dfs(t,h);
		dp[h][0]+=dp[t][1];
		dp[h][1]+=min(dp[t][0],dp[t][1]);
	}
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		ll num,k;
		scanf("%lld %lld",&num,&k);
		for(ll j=1;j<=k;j++){
			ll y;
			scanf("%lld",&y);
			add(num,y);
			add(y,num);
		}
	}
	dfs(0,-1);
	printf("%lld",min(dp[0][0],dp[0][1]));
	return 0;
}

A1579

A1579

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,home[1501],dp[1501][3],w[1501],cnt;
struct node{
	ll next,to;
}e[3001];
void add(ll a,ll b){
	e[++cnt].to=b;
	e[cnt].next=home[a];
	home[a]=cnt;
}
void dfs(ll h,ll fa){
	ll d=0x3f3f3f3f3f3f3f3f;
	for(ll i=home[h];i;i=e[i].next){
		ll t=e[i].to;
		if(t==fa) continue;
		dfs(t,h);
		dp[h][0]+=min(dp[t][1],dp[t][2]);
		dp[h][1]+=min(dp[t][1],dp[t][2]);
		dp[h][2]+=min(dp[t][0],min(dp[t][1],dp[t][2]));
		d=min(d,dp[t][2]-min(dp[t][1],dp[t][2]));
	}
	dp[h][2]+=w[h];
	dp[h][1]+=d;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		ll num,k;
		scanf("%lld",&num);
		scanf("%lld %lld",&w[num],&k); 
		for(ll j=1;j<=k;j++){
			ll y;
			scanf("%lld",&y);
			add(num,y);
			add(y,num);
		}
	}
	dfs(1,-1);
//	for(ll i=1;i<=n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	printf("%lld",min(dp[1][1],dp[1][2]));
	return 0;
}

P1563

P1563

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000007;
struct node{
	ll next,to;
}e[200001];
ll home[200001],cnt;
void add(ll a,ll b){
	e[++cnt].to=b;
	e[cnt].next=home[a];
	home[a]=cnt;
}
ll dp[200001][2];
void dfs(ll h,ll fa){
	dp[h][1]=dp[h][0]=1;
	for(ll i=home[h];i;i=e[i].next){
		ll t=e[i].to;
		if(t==fa) continue;
		dfs(t,h);
		dp[h][1]=(dp[h][1]*dp[t][0])%mod;
		dp[h][0]=dp[h][0]*((dp[t][1]+dp[t][0])%mod)%mod;
	}
}
int main(){
	ll n;
	scanf("%lld",&n);
	for(ll i=1;i<n;i++){
		ll a,b;
		scanf("%lld %lld",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	printf("%lld",(dp[1][1]+dp[1][0])%mod);
	return 0;
}