2 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 4e4 + 4, Q = 2e4 + 7; vector< pair<int, int> > G[N]; int n, L;ll ans; int siz[N], all, rt, rtmaxsiz; int dis[N], cnt; bool del[N]; 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) { if(w>L) return ; dis[++cnt] = w ; for (auto i:G[x]) if (i.first != xfa && !del[i.first]) getdis(i.first, x, w + i.second); } ll calc(int x,int w) { cnt = 0; getdis(x, 0, w); sort(dis + 1, dis + cnt + 1); int l = 1, r = cnt; ll res = 0; while (l < r) { if (dis[l] + dis[r] <= L) res += r - l, l++; else r--; } return res; } void divide(int x) { ans+=calc(x,0); del[x] = true; for (auto i:G[x]) if (!del[i.first]){ ans-=calc(i.first,i.second); 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 ; 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}); } cin >> L; ans = 0; all=rtmaxsiz=n;getroot(1, 0);getroot(rt, 0); divide(rt); cout << ans << "\n"; return 0; } -
-1
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back const int N=4e4+10; int n,k,rt,cnt,mg,all,ans; int sz[N],d[N];bool 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) { if(dis>k)return; 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); } } int calc(int x,int dis) { cnt=0;getd(x,0,dis); sort(d+1,d+cnt+1); int l=1,r=cnt,res=0; while(l<r) { if(d[l]+d[r]<=k) res+=r-l,l++; else r--; } return res; } void solve(int x) { v[x]=1;ans+=calc(x,0); for(auto i:e[x]) { int y=i.fi,w=i.se; if(v[y])continue; ans-=calc(y,w); mg=all=sz[y]; getg(y,0); getg(rt,x); solve(rt); } } int main() { scanf("%d",&n); 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}); } scanf("%d",&k); all=rt=n; getg(1,0); solve(rt); printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 3121
- 时间
- 200ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- 递交数
- 61
- 已通过
- 16
- 上传者