[BZOJ1316]
由于之前板子写得太烂了,今天把它重新整理改进了一下
vis[]
表示每个点是否已经当过根,所以注意 dfs,findroot
函数的计算过程中是不会对 vis
进行修改的
修改时只需要考虑对 dfs
和 solve
中的有关位置进行修改即可,其它部分基本不变
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define foradj(p) for(pair<int,int> pr:g[p])
#define unpii(q,w) int q=pr.first, w=pr.second;
const int N = 10005;
vector <pair<int,int> > g[N];
int dis[N],siz[N],n,m,t1,t2,t3,k[N],ans[N],vis[N],sum,rt,rtval;
vector<int> st,wl;
set<int> s;
void findroot(int p,int ff)
{
siz[p]=1;
int mx=0;
foradj(p)
{
unpii(q,w);
if(!vis[q] && q!=ff)
{
findroot(q,p);
siz[p]+=siz[q];
mx=max(mx,siz[q]);
}
}
mx=max(mx,sum-siz[p]);
if(mx<rtval) rtval=mx, rt=p;
}
void dfs(int p,int ff)
{
for(int i=1;i<=m;i++)
{
ans[i]|=s.count(k[i]-dis[p]);
st.push_back(dis[p]);
}
foradj(p)
{
unpii(q,w);
if(!vis[q] && q!=ff)
{
dis[q]=dis[p]+w;
dfs(q,p);
}
}
}
void solve(int p)
{
vis[p]=1;
s.clear();
foradj(p)
{
unpii(q,w);
if(!vis[q])
{
dis[q]=w;
dfs(q,p);
for(int i:st) s.insert(i);
st.clear();
}
}
for(int i=1;i<=m;i++)
{
ans[i]|=s.count(k[i]);
}
foradj(p)
{
unpii(q,w);
if(!vis[q])
{
sum=siz[q];
rtval=1e18;
findroot(q,0);
solve(rt);
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<n;i++)
{
cin>>t1>>t2>>t3;
g[t1].push_back({t2,t3});
g[t2].push_back({t1,t3});
}
for(int i=1;i<=m;i++)
{
cin>>k[i];
}
sum=n;
rtval=1e18;
findroot(1,0);
solve(rt);
for(int i=1;i<=m;i++)
{
if(ans[i] || !k[i]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
原文链接: https://www.cnblogs.com/mollnn/p/13267069.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/363886
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!