求助卡常 玄关 已破防
查看原帖
求助卡常 玄关 已破防
347664
菲斯斯夫斯基楼主2024/5/31 11:22

rt,应该是被卡常了,破防了,谢谢。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define fi first
#define se second
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
//	int k;
//	cin>>k;
//	return k;
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
const int N=2e5+10;
int n,m,root,ans,t,chk,mx;
int ma[N],vis[N],s[N],c[N],f[N],mp[N];
vector<pair<int,int>>v[N],now;
struct ccf
{
	int x,id,c;
};
inline int max(int x,int y)
{
	return x>y?x:y;
}
inline int min(int x,int y)
{
	return x<y?x:y;
}
inline int ask(int x)
{
	if(x<0)return 0;
	int ma=chk;
	for(;x;x-=x&-x)
		ma=max(ma,f[x]);
	return ma;
}
inline void change(int x,int y)
{
	if(x<0)return ;
	if(x==0)
	{
		chk=max(chk,y);
		return ;
	}
	for(;x<=m;x+=x&-x)
		f[x]=max(f[x],y);
}
inline void era(int x)
{
	if(x<0)return ;
	if(!x)return ;
	for(;x<=m;x+=x&-x)
		f[x]=0;
}
inline void find(int x,int fa,int sum)
{
	s[x]=1,ma[x]=0;
	for(auto i:v[x])
	{
		if(i.fi==fa||vis[i.fi])continue;
		find(i.fi,x,sum);
		s[x]+=s[i.fi];
		ma[x]=max(ma[x],s[i.fi]); 
	}
	ma[x]=max(ma[x],sum-s[x]);
	if(ma[x]<ma[root])root=x;
}
inline void dfs(int x,int fa,int k,int y,int id)
{
	if(y+c[id]>m)return ;
	now.push_back({k,y});
	mp[y+c[id]]=max(mp[y+c[id]],k);
	if(k>0)mx=max(mx,y+c[id]);
	for(auto i:v[x])
	{
		if(i.fi==fa||vis[i.fi])continue;
		dfs(i.fi,x,k+i.se,y+c[i.fi],id);
	}
}
inline void solve(int x)
{
	vis[x]=1;
	int last=0;
	for(auto i:v[x])
	{
		if(vis[i.fi])continue;
		mx=0;
		dfs(i.fi,x,i.se,c[i.fi],x);
		for(int j=0;j<=m;j++)
			if(mp[j])ans=max(ans,ask(m-j)+mp[j]);
		for(int j=0;j<=m;j++)
			if(mp[j])change(j-c[x],mp[j]),mp[j]=0;
	}
	chk=0;
	for(auto i:now)
		era(i.se);
	now.clear();
//	cout<<x<<':'<<ans<<endl;
	for(auto i:v[x])
	{
		if(vis[i.fi])continue;
		root=0;
		find(i.fi,x,s[i.fi]);
		solve(i.fi);
	}
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),m=read(),t=read();
	int x,y,z;
	while(t--)
		x=read(),c[x]=1;
	for(int i=1;i<n;i++)
	{
		x=read(),y=read(),z=read();
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	ma[0]=n;
	find(1,0,n),solve(root);
	cout<<ans;
	return 0;
}
2024/5/31 11:22
加载中...