P4178 Tree 问树上点权小于等于k的路径个数 #include <cstdio> #include <bitset> #include <cstring> #include <algorithm> using namespace std; const int maxd = 1e5; struct node { int v,net,dis; }e[maxd*2]; int f[maxd],eid,k; long long ans; int sz[maxd],son[maxd],d[maxd],vis[maxd],tot; int n,m,root,cnt,flag; void init() { memset(f,-1,sizeof(f)); eid = 0; } void insert(int a,int b,int dis) { e[eid].v = b; e[eid].net = f[a]; e[eid].dis = dis; f[a] = eid++; } void Get_Root(int x,int fa) //找根 { son[x] = 0,sz[x] = 1; for(int i=f[x];i+1;i=e[i].net) { int v = e[i].v; if(v==fa||vis[v]) continue; Get_Root(v,x); son[x] = max(son[x],sz[v]); sz[x] += sz[v]; } son[x] = max(son[x],tot - sz[x]); if(son[x] < son[root]) root = x; } void Get_dis(int x,int fa,int len) // 统计当前重心到各个点的距离 { for(int i=f[x];i+1;i=e[i].net) { int v = e[i].v; if(vis[v]||v == fa) continue; d[++cnt] = len + e[i].dis; Get_dis(v,x,d[cnt]); } } int find(int l,int r,int v) { int res = 0; while(l<=r) { int mid = (l+r)>>1; if(d[mid]<=v) res = mid, l = mid+1; else r = mid-1; } return res; } void Get_Ans(int x,int dis,int w) //统计当前点的符合条件数 { d[cnt=1] = dis; // 加入0,覆盖一条边的统计 Get_dis(x,0,dis); sort(d+1,d+1+cnt); while(cnt && d[cnt] > k) cnt--; while(cnt) ans += w*find(1,cnt-1,k-d[cnt]),cnt--; } void Point_Divid(int x) { vis[x] = 1; Get_Ans(x,0,1); for(int i=f[x];i+1;i=e[i].net) { int v = e[i].v; if(vis[v]) continue; Get_Ans(v,e[i].dis,-1); tot = sz[v];root = 0; Get_Root(v,x),Point_Divid(root); } } int main() { // freopen("a.in","r",stdin); // freopen("k.out","w",stdout); init(); scanf("%d",&n); for(int i=1;i<n;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); insert(x,y,z); insert(y,x,z); } scanf("%d",&k); tot = n; son[0] = 1e9;Get_Root(1,0); Point_Divid(root); printf("%lld",ans); return 0; }
Read More ~