bzoj1468

1468: Tree

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1023 Solved: 532
[Submit][Status][Discuss]

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k

Output

一行，有多少对点之间的距离小于等于k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10

Sample Output

HINT

Source

题解：

　　点分治裸题，那么什么是点分治呢

　　点分治

　　1、求树的重心
　　2、计算以当前重心为根的子树的答案
　　3、去掉以当前重心儿子为根的子树的答案
　　4、枚举每个儿子，分治

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define maxn 40005
 7 using namespace std;
 8 int n,k,i,j,tot,root,ans,L,all;
 9 int pre[maxn*2],now[maxn],v[maxn*2],val[maxn*2],son[maxn],f[maxn];
10 int dist[maxn],data[maxn];
11 bool vis[maxn];
12 int read()
13 {
14     int x=0; char ch; bool bo=0;
15     while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1;
16     while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9');
17     if (bo) return -x; return x;
18 }
19 void ins(int a,int b,int c){
20     pre[++tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
21 }
22 void get_root(int u,int fa)
23 {
24     son[u]=1; f[u]=0;
25     for (int p=now[u]; p; p=pre[p])
26     {
27         int vv=v[p];
28         if (vv==fa || vis[vv]) continue;
29         get_root(vv,u); son[u]+=son[vv];
30         f[u]=max(f[u],son[vv]);
31     }
32     f[u]=max(f[u],all-son[u]);
33     if (f[u]<f[root]) root=u;
34 }
35 void get_array(int u,int fa)
36 {
37     data[++L]=dist[u];
38     for (int p=now[u]; p; p=pre[p])
39     {
40         int vv=v[p];
41         if (vv!=fa&&!vis[vv]) 
42         dist[vv]=dist[u]+val[p],get_array(vv,u);
43     }
44 }
45 int calc(int u,int value)
46 {
47     dist[u]=value; L=0; get_array(u,-1); 
48     sort(data+1,data+1+L);
49     int preans=0,l=1,r=L;
50     while (l<r)
51     {
52         if (data[l]+data[r]<=k) preans+=(r-l),l++; else r--;
53     }
54     return preans;
55 }
56 void solve(int u)
57 {
58     ans+=calc(u,0); vis[u]=1;
59     //cout<<"        ans       "<<u<<endl;
60     for (int p=now[u]; p; p=pre[p])
61     {
62         int vv=v[p];
63         //cout<<"                   "<<vv<<endl;
64         if (vis[vv]) continue;
65         ans-=calc(vv,val[p]); f[root=0]=n+1; 
66         all=son[vv]; get_root(vv,-1);
67         solve(root);
68     }
69 }
70 int main()
71 {
72     n=read();
73     for (int i=1; i<=n-1; i++)
74     {
75         int u=read(),v=read(),value=read();
76         ins(u,v,value); ins(v,u,value);
77     }
78     k=read();
79     f[root=0]=n+1; all=n;
80     get_root(1,-1);
81     //cout<<"                "<<root<<endl;
82     solve(root);
83     printf("%d
",ans);
84     return 0;
85 }

View Code