1 条题解
-
0
#define ll long long using namespace std; const int N=1e4+5; int n; struct node{int v,w;}; vector<node>g[N]; bool vis[N]; int get_size(int u,int p)//返回子树的结点数 { if(vis[u])return 0; int sum=1; for(auto v:g[u]) if(v.v!=p) sum+=get_size(v.v,u); return sum; } int cal_wc(int u,int fa,int tot,int &wc)//寻找重心 重心为wc即时修改 tot为连通块结点总数 { if(vis[u]) return 0; int sum=1,ms=0;//ms为子树中最大的子树的结点数 sum为所有子树的结点总和 for(auto v:g[u]) { if(v.v!=fa) { int tmp=cal_wc(v.v,u,tot,wc);//子树结点数 sum+=tmp; ms=max(ms,tmp); } } ms=max(ms,tot-sum); if(ms<=tot/2)wc=u; return sum; } bool used[10000005]; int maxn=0; vector<int>cnt1; vector<int>cnt2; void dfs2(int u,int fa,int step) { if(vis[u]) return; if(step>10000000) return; used[step]=true; cnt2.push_back(step); for(auto v:g[u]) if(v.v!=fa) dfs2(v.v,u,step+v.w); } void dfs(int u)//寻找重心且往重心的子树递归 { if(vis[u]) return; cal_wc(u,-1,get_size(u,-1),u);//寻找该子树重心 //进行处理 cnt1.clear(); for(auto v:g[u]) { cnt2.clear(); dfs2(v.v,u,v.w); for(auto i:cnt1) for(auto j:cnt2) if(i+j>10000000) continue; else used[i+j]=true; for(auto i:cnt2) cnt1.push_back(i); } vis[u]=true;//标记重心 for(auto v:g[u]) dfs(v.v);//往下递归 } int main() { int T; scanf("%d%d",&n,&T); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs(1); while(T--) { int x; scanf("%d",&x); if(used[x]) puts("YES"); else puts("NO"); } return 0; }
- 1
信息
- ID
- 24
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 25
- 已通过
- 3
- 上传者