Loading... <!--more--> ### 思想 点分治是一种用于处理静态树上路径统计问题的算法，其核心原理还是基于分治思想。 我们不妨对这类树上静态路径统计问题抽象化，例如： > 给定一个棵无根树，求满足要求P的路径有几条(点对) 我们可以使用分治算法求解本题，对于无根树，我们指定一个节点为根，显然，这样的路径可以归为两类： > 1. 满足要求**P**且经过根**root**的路径 > 2. 满足要求**P**但不经过根**root**的路径 第二类路径不经过根，所以一定在根的某一刻子树中，这我们就可以递归地进行求解，而重点就在于统计第一类路径。 先不考虑统计问题，我们可以设计如下的分治算法： > 1. 求出根**root** > 2. 得到相关信息，统计第一类路径并累加入答案中 > 3. 删除节点**root** ，对于**root** 的每一棵子树递归的执行分治算法 显然，递归的层数和每一次选取的根**root**有关，当树退化成一条链时，如果任意的选取根，递归层数很可能就达到$O(n)$层。解决方法就是选取树的重心作为树的根，容易证明，每一次选取树的重心作为根时，点分治算法最多递归$log_2n$层。 一般我们有下面几种方法来计算以当前重心作为根对答案的贡献 ### 第一种 先一次性的计算出当前根$u$所有子树的贡献，这里面包括了经过当前树根的路径和不经过当前树根的路径，因此我们还要遍历$u$的所有子树，减去各个子树单独的贡献，即不经过当前树根$u$的路径数量。 [POJ1741](http://poj.org/problem?id=1741) 按照dis从小到大排序，对于每个i维护一个R使得区间[i+1,R]内所有点都满足，可知R是递减的，先算总的贡献，再减去各个子树的贡献。 ```cpp #include <cstdio> #include <cstring> #include <algorithm> #define ls (rt << 1) #define rs (rt << 1 | 1) #define lowbit( x ) (x&(-x)) #define SZ( v ) ((int)(v).size()) #define All( v ) (v).begin(), (v).end() #define mp( x , y ) make_pair(x,y) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair < int , int > P; const int N = 1e4 + 10; const int M = 1e6 + 10; const int mod = 998244353; const int inf = 0x3f3f3f3f; const int seed = 131; int n , m , k; int head[N] , tot , root , cnt , MX , ans , cursz , vis[N] , ver[N << 1] , w[N << 1] , nxt[N << 1] , sz[N]; ll dis[N] , dist[N]; void addedge ( int from , int to , int len ) { ver[++ tot] = to; w[tot] = len; nxt[tot] = head[from]; head[from] = tot; } void get ( int u , int fa ) { sz[u] = 1; int mx = 0; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { get ( v , u ); sz[u] += sz[v]; mx = max ( mx , sz[v] ); } } mx = max ( mx , cursz - sz[u] ); if ( mx < MX ) root = u , MX = mx; } void dfs1 ( int u , int fa ) { dist[++ cnt] = dis[u]; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { dis[v] = dis[u] + w[i]; dfs1 ( v , u ); } } } int cal ( int u ) { int res = 0; cnt = 0; dfs1 ( u , 0 ); sort ( dist + 1 , dist + cnt + 1 ); int L = 1 , R = cnt; while ( L < R ) { while ( L < R && dist[L] + dist[R] > k ) -- R; res += R - L; ++ L; } return res; } void dfs ( int u ) { vis[u] = 1; dis[u] = 0; ans += cal ( u ); get ( u , 0 ); for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] ) { //dis[v] = w[i]; ans -= cal ( v ); MX = inf; cursz = sz[v]; get ( v , 0 ); dfs ( root ); } } } int main () { int u , v , len; while ( scanf ( "%d%d" , &n , &k ) != EOF && ( n || k ) ) { tot = 0; root = 0; ans = 0; for ( int i = 0 ; i <= n ; ++ i ) head[i] = - 1 , vis[i] = 0; for ( int i = 1 ; i < n ; ++ i ) { scanf ( "%d%d%d" , &u , &v , &len ); addedge ( u , v , len ); addedge ( v , u , len ); } MX = inf; cursz = n; get ( 1 , 0 ); dfs ( root ); printf ( "%d\n" , ans ); } return 0; } ``` [HDU 5314](http://acm.hdu.edu.cn/showproblem.php?pid=5314) 按照最小值从小到大排序，对于i，所有在i之前，且最小值大于i的最大值-D都满足，所以二分**最大值-D**即可，为什么要满足在i之前呢，因为在i之后的无法保证最大值减去最小值小于等于D。列如i之后有一个j，(i,j)之间最小值肯定是i的最小值，最大值可能是i也可能是j，如果是j可能就不满足最大值减去最小值小于等于D。因此我们只处理i之前的，最后将答案乘2即可。 ```cpp #include<bits/stdc++.h> #define ls (rt << 1) #define rs (rt << 1 | 1) #define lowbit( x ) (x&(-x)) #define SZ( v ) ((int)(v).size()) #define All( v ) (v).begin(), (v).end() #define mp( x , y ) make_pair(x,y) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair < int , int > P; const int N = 1e5 + 10; const int M = 1e7 + 10; const int mod = 1e6 + 3; const int inf = 0x3f3f3f3f; const int INF = 2e9; const int seed = 131; int n , m , k; int head[N] , tot , root , MX , cursz , vis[N] , ver[N << 1] , w[N << 1] , nxt[N << 1] , sz[N]; ll ans; int a[N] , MAX[N] , MIN[N] , D; P tmp[N]; void addedge ( int from , int to , int len ) { ver[++ tot] = to; w[tot] = len; nxt[tot] = head[from]; head[from] = tot; } void get ( int u , int fa ) { sz[u] = 1; int mx = 0; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { get ( v , u ); sz[u] += sz[v]; mx = max ( mx , sz[v] ); } } mx = max ( mx , cursz - sz[u] ); if ( mx < MX ) root = u , MX = mx; } void dfs1 ( int u , int fa ) { if ( MAX[u] - MIN[u] <= D ) tmp[++ tot] = mp( MIN[u] , MAX[u] ); for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { MAX[v] = max ( MAX[u] , a[v] ); MIN[v] = min ( MIN[u] , a[v] ); dfs1 ( v , u ); } } } ll cal ( int u ) { ll res = 0; tot = 0; dfs1 ( u , 0 ); sort ( tmp + 1 , tmp + tot + 1 ); for ( int i = 1 ; i <= tot ; ++ i ) { int dis = lower_bound ( tmp + 1 , tmp + i + 1 , mp( tmp[i].second - D , 0 ) ) - tmp; res += i - dis; } return res; } void dfs ( int u ) { MAX[u] = MIN[u] = a[u]; vis[u] = 1; ans += cal ( u ); for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] ) { ans -= cal ( v ); MX = inf; cursz = sz[v]; get ( v , 0 ); dfs ( root ); } } } int main () { int u , v , len , T; scanf ( "%d" , &T ); while ( T -- ) { tot = 0; ans = 0; scanf ( "%d%d" , &n , &D ); for ( int i = 1 ; i <= n ; ++ i ) { scanf ( "%d" , &a[i] ); head[i] = - 1; vis[i] = 0; } for ( int i = 1 ; i < n ; ++ i ) { scanf ( "%d%d" , &u , &v ); addedge ( u , v , 0 ); addedge ( v , u , 0 ); } MX = inf; cursz = n; get ( 1 , 0 ); dfs ( root ); printf ( "%lld\n" , ans * 2 ); } return 0; } ``` ### 第二种 逐个处理当前根u的各个子树，处理到某一子树时，之前遍历过的子树信息已经保存下来了，可供当前子树使用，即是之前子树中的点与当前子树形成的贡献。每处理完一个子树，将其信息保存下来。 这种方法一般用于枚举点才能算出贡献的题目中，既是枚举一个点，利用某个东西求得与这个点满足关系的点有多少个。一般是求解无序对(u,v)的个数，既是(u,v)与(v,u) 是一样的。下面一种方法我们将看到有的(u,v)与(v,u) 是不一样的。 [SPOJ 1825](https://www.spoj.com/problems/FTOUR2/) 这题使用到了第二种方法。我们用树状数组保存访问<=i个拥挤点所经过道路的最大距离，对于每个子树中的每个点v，根到v经过了若干距离，同时访问了若干个拥挤点，我们可以利用树状数组查询(k-已访问的拥挤点)所经过的最大距离，再加上当前的距离，尝试更新最大值。 ```cpp #include<bits/stdc++.h> #define ls (rt << 1) #define rs (rt << 1 | 1) #define lowbit( x ) (x&(-x)) #define SZ( v ) ((int)(v).size()) #define All( v ) (v).begin(), (v).end() #define mp( x , y ) make_pair(x,y) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair < int , int > P; const int N = 2e5 + 10; const int M = 1e7 + 10; const int mod = 998244353; const int inf = 0x3f3f3f3f; const int INF = 2e9; const int seed = 131; int n , m , k; int tot , root , cnt[N] , cr[N] , MX , cursz , vis[N] , sz[N]; int dis[N] , ans , _k , tmp[N] , c[N]; P dist[N]; vector < P > G[N]; void add ( int x , int v ) { for ( ; x <= m + 1 ; x += lowbit( x ) ) c[x] = max ( c[x] , v ); } void del ( int x ) { for ( ; x <= m + 1 ; x += lowbit( x ) ) c[x] = - INF; } int ask ( int x ) { int res = - INF; for ( ; x > 0 ; x -= lowbit ( x ) ) res = max ( res , c[x] ); return res; } void get ( int u , int fa ) { sz[u] = 1; int mx = 0; for ( auto &E:G[u]) { int v = E.first; if ( ! vis[v] && v != fa ) { get ( v , u ); sz[u] += sz[v]; mx = max ( mx , sz[v] ); } } mx = max ( mx , cursz - sz[u] ); if ( mx < MX ) root = u , MX = mx; } void dfs1 ( int u , int fa ) { dist[++ tot] = mp( dis[u] , cnt[u] ); for ( auto &E:G[u] ) { int v = E.first , w=E.second; if ( ! vis[v] && v != fa ) { dis[v] = dis[u] + w; cnt[v] = cnt[u] + cr[v]; dfs1 ( v , u ); } } } void cal ( int u ) { dis[u] = 0; //cnt[u] = cr[u]; cnt[u] = 0; add ( 1 , 0 ); int tot1 = 0; tmp[++ tot1] = cnt[u] + 1; for ( auto &E:G[u] ) { int v = E.first , w = E.second; if ( ! vis[v] ) { dis[v] = w; cnt[v] = cnt[u] + cr[v]; tot = 0; dfs1 ( v , u ); for ( int j = 1 ; j <= tot ; ++ j ) { if ( k - ( dist[j].second + cr[u] ) + 1 > 0 ) { ans = max ( 1LL * ans , 1LL * dist[j].first + ask ( k - ( dist[j].second + cr[u] ) + 1 ) ); } } for ( int j = 1 ; j <= tot ; ++ j ) if ( dist[j].second <= k ) add ( dist[j].second + 1 , dist[j].first ) , tmp[++ tot1] = dist[j].second + 1; } } for ( int i = 1 ; i <= tot1 ; ++ i ) del ( tmp[i] ); } void dfs ( int u ) { vis[u] = 1; cal ( u ); for ( auto &E:G[u]) { int v = E.first; if ( ! vis[v] ) { MX = inf; cursz = sz[v]; get ( v , 0 ); dfs ( root ); } } } int main () { int u , v , len; scanf ( "%d%d%d" , &n , &k , &m ); for ( int i = 0 ; i <= m + 1 ; ++ i ) c[i] = - INF; for ( int i = 1 ; i <= m ; ++ i ) { scanf ( "%d" , &u ); cr[u] = 1; } for ( int i = 1 ; i < n ; ++ i ) { scanf ( "%d%d%d" , &u , &v , &len ); G[u].push_back ( mp( v , len ) ); G[v].push_back ( mp( u , len ) ); } MX = inf; cursz = n; get ( 1 , 0 ); dfs ( root ); printf ( "%d\n" , ans ); return 0; } ``` [HDU 4812](http://acm.hdu.edu.cn/showproblem.php?pid=4812) 将从根出发的乘积保存下来，直接使用即可(利用逆元) ### 第三种 这个同时结合了第一种和第二种方法，有时我们必须要枚举点才能算贡献，并且(u,v)和(v,u)不等价，我们就要用到这种方法了。我们通过一次dfs把u的所有子树保存下来，然后遍历到某个子树时，我们先删去这个子树的信息，然后遍历这个子树所有点，计算答案，遍历完后，将信息恢复。 [codeforce 716E](https://codeforces.com/contest/716/problem/E) 本题u->v和v->u形成的数是不一样的，所以对答案的贡献都要计算。参考:[题解](https://oi.men.ci/cf-716e/) ```cpp #include<bits/stdc++.h> #define ls (rt << 1) #define rs (rt << 1 | 1) #define lowbit( x ) (x&(-x)) #define SZ( v ) ((int)(v).size()) #define All( v ) (v).begin(), (v).end() #define mp( x , y ) make_pair(x,y) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair < int , int > P; const int N = 1e5 + 10; const int M = 1e7 + 10; const int mod = 1e6 + 3; const int inf = 0x3f3f3f3f; const int INF = 2e9; const int seed = 131; int n , m , k; int head[N] , tot , root , MX , cursz , vis[N] , ver[N << 1] , w[N << 1] , nxt[N << 1] , sz[N]; int dep[N] , tmp[N]; P dist[N]; ll a[N] , b[N] , c[N] , inv10[N] , exp10[N] , ans; /* b[i]*10^(dep)+a[i]=0(%m) b[i] = -a[i]/(10^(dep))%m = (m-a[i])/(10^(dep)) a[i]: 从根到i b[i]: 从i到根 c[i]: */ map < ll , int > mp; void addedge ( int from , int to , int len ) { ver[++ tot] = to; w[tot] = len; nxt[tot] = head[from]; head[from] = tot; } int exgcd ( int a , int b , int &x , int &y ) { if ( ! b ) { x = 1; y = 0; return a; } int d = exgcd ( b , a % b , y , x ); y -= ( a / b ) * x; return d; } void get ( int u , int fa ) { sz[u] = 1; int mx = 0; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { get ( v , u ); sz[u] += sz[v]; mx = max ( mx , sz[v] ); } } mx = max ( mx , cursz - sz[u] ); if ( mx < MX ) root = u , MX = mx; } void dfs1 ( int u , int fa ) { for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) { dep[v] = dep[u] + 1; a[v] = ( a[u] * 10 + w[i] ) % m; b[v] = ( exp10[dep[v] - 1] * w[i] + b[u] ) % m; c[v] = 1LL * ( m - a[v] ) % m * inv10[dep[v]] % m; dfs1 ( v , u ); } } } void add ( int u , int fa , int val ) { mp[c[u]] += val; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) add ( v , u , val ); } } void solve ( int u , int fa ) { if ( mp.count ( b[u] ) ) ans += mp[b[u]]; for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] && v != fa ) solve ( v , u ); } } void cal ( int u ) { a[u] = b[u] = c[u] = dep[u] = 0; mp.clear (); dfs1 ( u , 0 ); add ( u , 0 , 1 ); for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] ) { add ( v , u , - 1 ); solve ( v , u ); add ( v , u , 1 ); } } ans += mp[0] - 1;//从根出发的答案 //add ( u , 0 , - 1 ); } void dfs ( int u ) { vis[u] = 1; cal ( u ); for ( int i = head[u] ; i != - 1 ; i = nxt[i] ) { int v = ver[i]; if ( ! vis[v] ) { MX = inf; cursz = sz[v]; get ( v , 0 ); dfs ( root ); } } } int main () { int u , v , len; int inv , t; scanf ( "%d%d" , &n , &m ); exgcd ( 10 , m , inv , t ); inv = ( inv%m + m ) % m; inv10[0] = exp10[0] = 1; for ( int i = 1 ; i <= n ; ++ i ) { exp10[i] = exp10[i - 1] * 10 % m; inv10[i] = inv10[i - 1] * inv % m; } for ( int i = 1 ; i <= n ; ++ i ) head[i] = - 1; for ( int i = 1 ; i < n ; ++ i ) { scanf ( "%d%d%d" , &u , &v , &len ); ++ u , ++ v; addedge ( u , v , len ); addedge ( v , u , len ); } MX = inf; cursz = n; get ( 1 , 0 ); dfs ( root ); printf ( "%lld\n" , ans ); return 0; } ``` Last modification：January 28th, 2020 at 11:32 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
