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 ~
标签:#
点分治