首页 > > 程序设计 > C/C++ >

codeforces293E Close Vertices -- 点分治+树状…

2018-06-17 23:19:25来源：未知阅读 ()

题目大意：

给出一棵树，每条边有权值，求经过少于l条边，权值和少于w的路径总数。

点分治。每次求出所有点到重心的距离，按w排序，然后维护一个树状数组，记录经过的边<=i的点个数。由于可能两个点都在一棵子树中，再容斥一下就好了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline char nc(){
 7   static char buf[100000],*p1=buf,*p2=buf;
 8   if(p1==p2){
 9     p2=(p1=buf)+fread(buf,1,100000,stdin);
10     if(p1==p2)return EOF;
11   }
12   return *p1++;
13 }
14 inline void Read(int& x){
15   char c=nc();
16   for(;c<'0'||c>'9';)c=nc();
17   for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
18 }
19 #define N 100001
20 #define lowbit(x) x&-x
21 #define ll long long
22 struct Edge{
23   int t,nx,w;
24 }e[N<<1];
25 struct Node{
26   int d,w;
27 }a[N];
28 int i,j,k,n,m,h[N],f[N],L,w,Son[N],Sum,Num,x,y,t,c[N],Rt,l,r,M;
29 bool b[N];
30 ll Ans;
31 inline void Add(int x,int y,int z){
32   e[++Num].t=y;e[Num].w=z;e[Num].nx=h[x];h[x]=Num;
33 }
34 inline int _Max(int x,int y){return x>y?x:y;}
35 inline int _Min(int x,int y){return x>y?y:x;}
36 inline bool Cmp(Node a,Node b){return a.w<b.w;}
37 inline void Update(int x,int y){if(x==0)return;for(;x<=M;x+=lowbit(x))c[x]+=y;}
38 inline int Query(int x){int Ans=0;for(;x>0;x-=lowbit(x))Ans+=c[x];return Ans;}
39 inline void Get_root(int x,int F){
40   f[x]=0;Son[x]=1;
41   for(int i=h[x];i;i=e[i].nx){
42     int v=e[i].t;
43     if(e[i].t==F||b[e[i].t])continue;
44     Get_root(e[i].t,x);Son[x]+=Son[e[i].t];
45     f[x]=_Max(f[x],Son[e[i].t]);
46   }
47   f[x]=_Max(f[x],Sum-Son[x]);
48   if(f[x]<f[Rt])Rt=x;
49 }
50 inline void Dfs(int x,int F,int y,int z){
51   if(F!=0){a[++t].d=y;a[t].w=z;M=_Max(M,y);}
52   for(int i=h[x];i;i=e[i].nx){
53     int v=e[i].t;
54     if(v==F||b[v])continue;
55     Dfs(v,x,y+1,z+e[i].w);
56   }
57 }
58 inline ll Calc(int x,int y,int z,bool Flag){
59   t=M=0;if(Flag)Dfs(x,0,y,z);else Dfs(x,-1,y,z);
60   sort(a+1,a+t+1,Cmp);
61   l=1;r=t;ll Ans=0;
62   for(int i=1;i<=M;i++)c[i]=0;
63   for(int i=l;i<=r;i++)Update(a[i].d,1);
64   if(Flag)for(int i=l;i<=r;i++)if(a[i].w<=w&&a[i].d<=L)Ans++;
65   while(l<r)
66   if(a[l].w+a[r].w<=w){
67     Update(a[l].d,-1);
68     Ans+=Query(_Min(L-a[l++].d,M));
69   }else Update(a[r--].d,-1);
70   return Ans;
71 }
72 inline void Solve(int x){
73   b[x]=1;
74   Ans+=Calc(x,0,0,1);
75   for(int i=h[x];i;i=e[i].nx){
76     int v=e[i].t;
77     if(b[v])continue;
78     Ans-=Calc(v,1,e[i].w,0);
79     f[Rt=0]=n+1;Sum=Son[v];Get_root(v,0);
80     Solve(Rt);
81   }
82 }
83 int main()
84 {
85   Read(n);Read(L);Read(w);
86   for(i=1;i<n;i++){
87     Read(x);Read(y);
88     Add(i+1,x,y);
89     Add(x,i+1,y);
90   }
91   f[Rt=0]=n+1;Sum=n;Get_root(1,0);
92   Solve(Rt);
93   printf("%I64d",Ans);
94   return 0;
95 }