5 条题解
-
1
#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 4, M = 105, Q = 1e7 + 7; vector<pair<int, int> > G[N]; int n, m; int siz[N]/*以各店为根的子树大小*/, all/*整棵子树点数*/, rt/*根*/, rtmaxsiz/*用于跟新重心*/; int dis[N]/*各店到根的距离*/, cnt/*统计子树中dis个数*/; bool del[N]/*标记用过的点*/, mk[Q]/*标记路径长度是否存在*/; int ask[M]/*询问*/; bool ans[M]/*回答*/; void getroot(int x, int xfa)/*计算未被标记点中重心*/ { siz[x] = 1;/*初始化子树大小*/ int xmaxsiz = 0; for (auto i : G[x]) if (i.first != xfa and !del[i.first]/*节点是否合法*/) { getroot(i.first, x); siz[x] += siz[i.first];/*统计子树大小*/; xmaxsiz = max(xmaxsiz, siz[i.first]);/*更新"重儿子"*/ } xmaxsiz = max(xmaxsiz, all - siz[x]);/*更新最大连通块大小*/ if (xmaxsiz < rtmaxsiz) rtmaxsiz = xmaxsiz, rt = x;/*更新重心与最大连通块最小值*/ } void getdis(int x, int xfa, int w)/*跟新x节点到根距离为w时的x子树中到根距离*/ { dis[++cnt] = w;//dfs顺求到根节点距离 for (auto i : G[x]) if (i.first != xfa and !del[i.first]/*节点是否合法*/) getdis(i.first, x, w + i.second); } void calc(int x)/*统计根为x点时过根节点的路径距离*/ { mk[0] = true;/*长度为0的路径存在， 便于之后统计*/ cnt = 0; for (auto i : G[x]) if (!del[i.first]) { int oldcnt = cnt;/*前面子树的大小*/ getdis(i.first, x, i.second);/*统计以x为根子树节点到x的距离*/ for (int q = 1; q <= m; q++)/*遍历询问*/ for (int j = oldcnt + 1; j <= cnt and !ans[q]; j++)/*枚举距离*/ if (ask[q] >= dis[j]) ans[q] = ans[q] or mk[ask[q] - dis[j]];/*更新路径长度桶*/ while (++oldcnt <= cnt) if (dis[oldcnt] < Q)/*防止越界*/ mk[dis[oldcnt]] = true;/*补充这一课子树的贡献路径长度*/ } for (int i = 1; i <= cnt; i++) if (dis[i] < Q) mk[dis[i]] = false;/*清空数组*/; } void divide(int x) /*分治*/ { calc(x);/*先计算经过根节点的路径*/ del[x] = true; /*标记x点为已用过*/ /*分治统计不经过根节点的路径*/ for (auto i : G[x]) if (!del[i.first]) { all = rtmaxsiz = siz[i.first]; getroot(i.first, 0); getroot(rt, x);/*求子树中的重心*/ divide(rt); } } int main() { cin >> n >> m; for (int i = 1, x, y, w; i <= n - 1; i++) { cin >> x >> y >> w; G[x].push_back({y, w}); G[y].push_back({x, w}); } for (int i = 1; i <= m; i++) cin >> ask[i], ans[i] = false;/*输入询问，初始化答案*/ all = rtmaxsiz = n;/*先算整棵树*/ getroot(1, 0); getroot(rt, 0); divide(rt); for (int i = 1; i <= m; i++) cout << (ans[i] ? "Yes\n" : "No\n"); return 0; } -
1
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 4, M = 105, Q = 1e7 + 7; vector< pair<int, int> > G[N]; int n, m; int siz[N], all, rt, rtmaxsiz;//找子树的重心 int dis[N], cnt;//存子树中所有点到子树根的距离 bool del[N], mk[Q];//del表示每次删除的中心点 mk存长度桶 int ask[M];bool ans[M];//ask存每次询问，ans存每次询问的答案 void getroot(int x, int xfa) { siz[x] = 1; int xmaxsiz = 0; for (auto i:G[x]) if (i.first != xfa && !del[i.first]){ getroot(i.first, x); siz[x] += siz[i.first]; xmaxsiz = max(xmaxsiz, siz[i.first]); } xmaxsiz = max(xmaxsiz, all - siz[x]); if (xmaxsiz < rtmaxsiz) rtmaxsiz = xmaxsiz, rt = x; } void getdis(int x, int xfa, int w) { dis[++cnt] = w; for (auto i:G[x]) if (i.first != xfa && !del[i.first]) getdis(i.first, x, w + i.second); } void calc(int x) { mk[0] = true, cnt = 0; for (auto i:G[x]) if (!del[i.first]) { int oldcnt = cnt; getdis(i.first, x, i.second); for (int q = 1; q <= m; q++) for (int j = oldcnt+1; j <= cnt && !ans[q]; j++) if (ask[q] >= dis[j]) ans[q] |=mk[ask[q] - dis[j]] ; while (++oldcnt <= cnt) if (dis[oldcnt] < Q) mk[dis[oldcnt]] = true; } for(int i = 1; i <= cnt; i++) if (dis[i] < Q) mk[dis[i]] = false; } void divide(int x) { calc(x); del[x] = true; for (auto i:G[x]) if (!del[i.first]){ all=rtmaxsiz=siz[i.first];getroot(i.first, 0);getroot(rt, x); divide(rt); } } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> m; for (int i = 2, x, y, w; i <= n; i++) { cin >> x >> y >> w; G[x].push_back({y, w}); G[y].push_back({x, w}); } for (int i = 1; i <= m; i++) cin >> ask[i],ans[i] = false; all=rtmaxsiz=n;getroot(1, 0);getroot(rt, 0); divide(rt); for (int i = 1; i <= m; i++) cout << (ans[i] ? "Yes\n" : "No\n"); return 0; } -
0
// Splay 提醒：开启 O2 优化 #include <iostream> #include <algorithm> using namespace std; #define N 200005 #define INF 2147483647 #define ls(x) tr[x].s[0] #define rs(x) tr[x].s[1] struct node{ int s[2], p; int v, siz; void init(int p1, int v1){ p=p1; v=v1; siz=1; } }tr[N*40]; int n, m, w[N], idx; inline void pushup(int x){ tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1; } inline void rotate(int x){ int y=tr[x].p,z=tr[y].p; int k=tr[y].s[1]==x; tr[z].s[tr[z].s[1]==y]=x, tr[x].p=z; tr[y].s[k]=tr[x].s[k^1], tr[tr[x].s[k^1]].p=y; tr[x].s[k^1]=y, tr[y].p=x; pushup(y), pushup(x); } inline void splay(int &root,int x,int k){ while(tr[x].p != k){ int y=tr[x].p,z=tr[y].p; if(z != k) if((rs(y)==x)^(rs(z)==y)) rotate(x); else rotate(y); rotate(x); } if(!k) root=x; } inline void insert(int &root,int v){ int u=root,p=0; while(u) p=u,u=tr[u].s[v>tr[u].v]; u = ++idx; tr[p].s[v>tr[p].v]=u; tr[u].init(p,v); splay(root,u,0); } inline void del(int &root,int v){ int u=root; while(u){ if(tr[u].v==v) break; if(tr[u].v<v) u=rs(u); else u=ls(u); } splay(root,u,0); int l=ls(u),r=rs(u); while(rs(l)) l=rs(l); while(ls(r)) r=ls(r); splay(root,l,0); splay(root,r,l); ls(r)=0; splay(root,r,0); } inline int getrank(int root,int v){ int u=root,res=0; while(u){ if(tr[u].v<v) res+=tr[ls(u)].siz+1,u=rs(u); else u=ls(u); } return res; } inline int getpre(int root,int v){ int u=root,res=-INF; while(u){ if(tr[u].v<v) res=tr[u].v,u=rs(u); else u=ls(u); } return res; } inline int getnxt(int root,int v){ int u=root,res=INF; while(u){ if(tr[u].v>v) res=tr[u].v,u=ls(u); else u=rs(u); } return res; } //////////线段树 #define lc u<<1 #define rc u<<1|1 int root[N*4]; void build(int u,int l,int r){ insert(root[u],-INF), insert(root[u],INF); for(int i=l;i<=r;i++)insert(root[u],w[i]); if(l==r) return; int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); } int queryrank(int u,int l,int r,int x,int y,int v){ if(x<=l && r<=y) return getrank(root[u],v)-1; int mid=l+r>>1, res=0; if(x<=mid) res += queryrank(lc,l,mid,x,y,v); if(y>mid) res += queryrank(rc,mid+1,r,x,y,v); return res; } int queryval(int u,int x,int y,int k){ int l=0, r=1e8, ans; //二分 while(l<=r){ int mid=l+r>>1; if(queryrank(1,1,n,x,y,mid)+1<=k) l=mid+1, ans=mid; else r=mid-1; } return ans; } void change(int u,int l,int r,int pos,int v){ del(root[u],w[pos]); insert(root[u],v); if(l==r) return; int mid=l+r>>1; if(pos<=mid) change(lc,l,mid,pos,v); else change(rc,mid+1,r,pos,v); } int querypre(int u,int l,int r,int x,int y,int v){ if(x<=l && r<=y) return getpre(root[u],v); int mid=l+r>>1, res=-INF; if(x<=mid) res=max(res,querypre(lc,l,mid,x,y,v)); if(y>mid) res=max(res,querypre(rc,mid+1,r,x,y,v)); return res; } int querynxt(int u,int l,int r,int x,int y,int v){ if(x<=l && r<=y) return getnxt(root[u],v); int mid=l+r>>1, res=INF; if(x<=mid) res=min(res,querynxt(lc,l,mid,x,y,v)); if(y>mid) res=min(res,querynxt(rc,mid+1,r,x,y,v)); return res; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); while(m -- ){ int op,x,y,v; scanf("%d",&op); if(op==3)scanf("%d%d",&x,&v); else scanf("%d%d%d",&x,&y,&v); if(op==1) printf("%d\n",queryrank(1,1,n,x,y,v)+1); if(op==2) printf("%d\n",queryval(1,x,y,v)); if(op==3) change(1,1,n,x,v), w[x]=v; if(op==4) printf("%d\n",querypre(1,1,n,x,y,v)); if(op==5) printf("%d\n",querynxt(1,1,n,x,y,v)); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; constexpr int N=1e4+10,M=1e7+10; vector<pair<int,int> >G[N]; int n,m,cnt,mxs,sum,root; int siz[N],dis[N],ans[N],d[N],del[N],query[N]; int q[M],judge[M]; inline void getroot(int x,int xfa){//寻找树的重心 siz[x]=1; int s=0; for(auto i:G[x]) if(i.first!=xfa&&!del[i.first]){ int y=i.first,z=i.second; getroot(y,x); siz[x]+=siz[y]; s=max(s,siz[y]); } s=max(s,sum-siz[x]); if(s<mxs){ mxs=s; root=x; } } inline void getdis(int x,int xfa){//计算到子树或整棵树的根节点距离 dis[++cnt]=d[x]; for(auto i:G[x]) if(i.first!=xfa&&!del[i.first]){ int y=i.first,z=i.second; d[y]=d[x]+z; getdis(y,x); } } inline void calc(int x){//处理经过子树或整棵树根节点的路径并回复询问 del[x]=judge[0]=1; int p=0; for(auto i:G[x]) if(!del[i.first]){ int y=i.first,z=i.second; cnt=0; d[y]=z; getdis(y,x); for(int j=1;j<=cnt;j++){ for(int k=1;k<=m;k++){ if(query[k]>=dis[j]) ans[k]|=judge[query[k]-dis[j]]; } } for(int j=1;j<=cnt;j++) if(dis[j]<M){ q[++p]=dis[j]; judge[dis[j]]=1; } } for(int i=1;i<=p;i++) judge[q[i]]=0; } inline void divide(int x){//分治 calc(x); for(auto i:G[x]) if(!del[i.first]){ int y=i.first,z=i.second; mxs=sum=siz[y]; getroot(y,0); divide(root); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); G[x].push_back({y,z}); G[y].push_back({x,z}); } for(int i=1;i<=m;i++){//记录询问 scanf("%d",&query[i]); ans[i]=0; } mxs=sum=n; getroot(1, 0);getroot(root, 0); divide(root); for(int i=1;i<=m;i++){//依次回复询问 if(ans[i]) puts("Yes"); else puts("No"); } } -
-1
duanjiahui2024
LV 10
@ 2025-12-28 11:24:08
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back const int N=1e4+10,M=1e7+10; int n,m,rt,cnt,mg,all; int sz[N],d[N],q[N]; bool f[N],bk[M],v[N]; vector<pair<int,int> >e[N]; void getg(int x,int xfa) { int g=0;sz[x]=1; for(auto i:e[x]) { int y=i.fi; if(v[y]||y==xfa)continue; getg(y,x); sz[x]+=sz[y]; g=max(g,sz[y]); } g=max(g,all-sz[x]); if(g<mg)mg=g,rt=x; } void getd(int x,int xfa,int dis) { d[++cnt]=dis; for(auto i:e[x]) { int y=i.fi,w=i.se; if(v[y]||y==xfa)continue; getd(y,x,w+dis); } } void calc(int x) { bk[0]=1;cnt=0; for(auto i:e[x]) { int y=i.fi,w=i.se; if(v[y])continue; int l=cnt;getd(y,x,w); for(int i=1;i<=m;i++)for(int j=l+1;j<=cnt;j++) if(q[i]>=d[j])f[i]|=bk[q[i]-d[j]]; for(int i=l+1;i<=cnt;i++) if(d[i]<M)bk[d[i]]=1; } for(int i=1;i<=cnt;i++) if(d[i]<M)bk[d[i]]=0; } void solve(int x) { v[x]=1;calc(x); for(auto i:e[x]) { int y=i.fi; if(v[y])continue; mg=all=sz[y]; getg(y,0); getg(rt,x); solve(rt); } } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y,w;i<n;i++) { scanf("%d%d%d",&x,&y,&w); e[x].pb({y,w}); e[y].pb({x,w}); } for(int i=1;i<=m;i++)scanf("%d",&q[i]); all=rt=n;getg(1,0); solve(rt); for(int i=1;i<=m;i++) { if(f[i])puts("Yes"); else puts("No"); } return 0; }
dengyanzhi2024
LV 8
@ 2025-12-30 23:13:05
- 1
