首页 > 代码库 > BZOJ1468 Tree

BZOJ1468 Tree

2024-08-09 02:14:12   211人阅读

典型的点分治。。。可惜有一部不会做。。。

如何找出某个点p的子树中过p的链的数量？、、、（语文不好不要打我）

于是Orz cxjyxx，可以先求出所有的答案再减掉不是的答案（说了语文不好不要打我了啊>_<）

其实貌似可以用点分树来写。。。的说？

 

技术分享
  1 /**************************************************************  2     Problem: 1468  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:756 ms  7     Memory:2528 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 40005; 15   16 struct edge { 17     int next, to, v; 18     edge() {} 19     edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 20 } e[N << 1]; 21   22 int first[N], tot; 23   24 struct tree_node { 25     int sz, dep; 26     bool vis; 27 } tr[N]; 28   29 int n, k, ans; 30 int dep[N], cnt_dep; 31 int Root, Maxsz; 32   33 inline int read() { 34     int x = 0; 35     char ch = getchar(); 36     while (ch < ‘0‘ || ‘9‘ < ch) 37         ch = getchar(); 38     while (‘0‘ <= ch && ch <= ‘9‘) { 39         x = x * 10 + ch - ‘0‘; 40         ch = getchar(); 41     } 42     return x; 43 } 44   45 void Add_Edges(int x, int y, int z) { 46     e[++tot] = edge(first[x], y, z), first[x] = tot; 47     e[++tot] = edge(first[y], x, z), first[y] = tot; 48 } 49   50 void dfs(int p, int fa, int sz) { 51     int x, y, maxsz = 0; 52     tr[p].sz = 1; 53     for (x = first[p]; x; x = e[x].next) 54         if ((y = e[x].to) != fa && !tr[y].vis) { 55             dfs(y, p, sz); 56             tr[p].sz += tr[y].sz; 57             maxsz = max(maxsz, tr[y].sz); 58         } 59     maxsz = max(maxsz, sz - tr[p].sz); 60     if (maxsz < Maxsz) 61         Root = p, Maxsz = maxsz; 62 } 63   64 int get_root(int p, int sz) { 65     Maxsz = N << 1; 66     dfs(p, 0, sz); 67     return Root; 68 } 69   70 void get_dep(int p, int fa) { 71     int x, y; 72     dep[++cnt_dep] = tr[p].dep; 73     for (x = first[p]; x; x = e[x].next) 74         if ((y = e[x].to) != fa && !tr[y].vis) { 75             tr[y].dep = tr[p].dep + e[x].v; 76             get_dep(y, p); 77         } 78 } 79   80 int cal(int p, int now) { 81     tr[p].dep = now, cnt_dep = 0; 82     get_dep(p, 0); 83     sort(dep + 1, dep + cnt_dep + 1); 84     int res = 0, l, r; 85     for (l = 1, r = cnt_dep; l < r; ) 86         if (dep[l] + dep[r] <= k) 87             res += r - l, ++l; 88         else --r; 89     return res; 90 } 91   92 void work(int p, int sz) { 93     int root = get_root(p, sz), x, y; 94     ans += cal(root, 0); 95     tr[root].vis = 1; 96     for (x = first[root]; x; x = e[x].next) 97         if (!tr[y = e[x].to].vis) { 98             ans -= cal(y, e[x].v); 99             work(y, tr[p].sz);100         }101 }102  103 int main() {104     int i, x, y, z;105     n = read();106     for (i = 1; i < n; ++i) {107         x = read(), y = read(), z = read();108         Add_Edges(x, y, z);109     }110     k = read();111     work(1, n);112     printf("%d\n", ans);113     return 0;114 }
View Code

 

BZOJ1468 Tree


联系
我们