洛谷 4178: Tree

2018-03-06Chentiancai_nn?

题目描述

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

输入输出格式

输入格式:

$N(n \leq 40000)$ 接下来$n-1$行边描述管道,按照题目中写的输入 接下来是$k$

输出格式:

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

输入输出样例

输入样例#1:

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

输出样例#1:

5

题解

这是一道点分治的教程题,可以用来讲解点分。但是我懒。
$d$数组用来存每次点分从根到节点的距离,$deep$数组用来存每次点分的所有权值。统计答案的时候就是经过根节点的两个路径和小于$k$就统计答案。就这样了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}
return x*f;
}
#define inf 0x3f3f3f3f
const int N = 40005;
int head[N],nxt[N*2],to[N*2],w[N*2],cnt;
int n,len,k,root,sum,ans,f[N],vis[N],son[N],d[N],deep[N];
void add(int x,int y,int z){ to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; w[cnt] = z; }
void getroot(int x,int fa){
son[x] = 1; f[x] = 0;
for(int i = head[x];i;i = nxt[i]){
if(to[i] == fa || vis[to[i]]) continue;
getroot(to[i],x);
son[x] += son[to[i]];
f[x] = max(f[x],son[to[i]]);
}
f[x] = max(f[x],sum-son[x]);
if(f[x] < f[root]) root = x;
}
void getdeep(int x,int fa){
deep[++deep[0]] = d[x];
for(int i = head[x];i;i = nxt[i]){
if(to[i] == fa || vis[to[i]]) continue;
d[to[i]] = d[x]+w[i];
getdeep(to[i],x);
}
}
int cal(int x,int v){
d[x] = v; deep[0] = 0;
getdeep(x,0);
sort(deep+1,deep+deep[0]+1);
int l = 1,r = deep[0],sum = 0;
while(l <= r){
if(deep[l]+deep[r] <= k){ sum += r-l; ++l; }
else --r;
}
return sum;
}
void solve(int x){
ans += cal(x,0);
vis[x] = 1;
for(int i = head[x];i;i = nxt[i]) if(!vis[to[i]]){
ans -= cal(to[i],w[i]);
sum = son[to[i]];
root = 0;
getroot(to[i],0);
solve(root);
}
}

int main(){
n = read();
for(int i = 1;i < n;++i){
int x = read(),y = read(),z = read();
add(x,y,z); add(y,x,z);
}
f[0] = inf; sum = n; k = read();
getroot(1,0);
solve(root);
printf("%d\n", ans);
return 0;
}

检测到你还在使用百度这个搜索引擎,
做为一个程序员,这是一种自暴自弃!

作环保的程序员,从不用百度开始!

Close