bzoj1468 Tree

Posted on |

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

假设我们按重心把树分成了若干子树，那么所要求得顶点对必居下面三者其一

  1. 属于同一子树的顶点对(v,w)。
    • 递归解决。
  2. 属于不同子树的顶点对(v,w)。
    • 方法很多，比如直接对所有点按照距离重心距离排序，然后枚举所有点，二分即可，别忘了减去①中的点对，或者用平衡树实现。
  3. 重心s和其他顶点v组成的顶点对(s,v)。
    • 额外添加一个距离s为零的结点，转化为情况2。

复杂度分析：

对于树分治，由于一棵树的重心保证最大的子树大小不会超过整棵树的一半，所以我们每对一个联通块找重心并删重心可以将这个联通块划分为至少2个，一次最少删除两条边，因而分为单独的顶点至多需要$\frac{n}{2}$次，总共遍历的点数为

$ \frac{n}{2} + (\frac{n}{2} + \frac{n}{2^2}) + (\frac{n}{2} + \frac{n}{2^2} + \frac{n}{2^3}) + (\frac{n}{2} + \frac{n}{2^2} + \frac{n}{2^3} + \frac{n}{2^4})+… \\= \frac{n}{2} \times logn +\frac{n}{2^2} \times (logn-1) + \frac{n}{2^3} \times (logn-2) + \frac{n}{2^4} \times (logn-3)+… \\=n\times \frac{logn\times (2^{logn}-1) + (logn-1)\times {2^{logn-2}} +(logn-3) \times 2^{logn-3}+…}{2^{logn}} \\=n\times \frac{logn \times 2^{logn-1} + logn \times 2^{logn-2} -2^{logn-2} + logn \times 2^{logn-3} - 2^{logn-3}+…}{2^{logn}}\\=n \times \frac{logn \times (2^{logn}-1) - (2^{logn-1}-1)}{2^{logn}} \\ \approx n\times(logn-\frac{1}{2}) \\ \approx nlogn$

再加上统计点对的时候二分所用的$logn$，总的复杂度为$O(nlog^2n)$

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
const int maxn=40000+5;
 
inline int readInt()
{
    char c;int tmp=0,x=1;c=getchar();
    while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
    while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
    return tmp*x;
}
 
typedef pair<int ,int > pii;
#define MP make_pair
#define fir first
#define sec second
 
int n,head[maxn],nxt[maxn<<1],eg[maxn<<1],tot=0,W[maxn<<1],K;
void addedge(int u,int v,int w)
{
    eg[++tot]=v;nxt[tot]=head[u];W[tot]=w;head[u]=tot;
    eg[++tot]=u;nxt[tot]=head[v];W[tot]=w;head[v]=tot;
}
bool Isc[maxn];
int ans,siz[maxn],par[maxn],parsiz=0,all[maxn],allsiz=0;
int Cal_Size(int v,int fa)
{
    int SIZ=1;
    for(int i=head[v];i;i=nxt[i]) {
        int u=eg[i];
        if(u!=fa && !Isc[u]) SIZ+=Cal_Size(u,v);
    }
    return siz[v]=SIZ;
}
pii Find_Centroid(int v,int fa,int ALL)
{
     int maxsiz=0,sum=1;
     pii ret=MP(INT_MAX,-1);
     for(int i=head[v];i;i=nxt[i]) {
         int u=eg[i];
         if(u!=fa && !Isc[u]) {
             ret=min(ret,Find_Centroid(u,v,ALL));
             sum+=siz[u];
             maxsiz=max(maxsiz,siz[u]);
         }
     }
     maxsiz=max(maxsiz,ALL-sum);
     ret=min(ret,MP(maxsiz,v));
     return ret;
}
void Cal_Dist(int v,int fa,int precost)
{
    par[parsiz++]=precost;
    for(int i=head[v];i;i=nxt[i]) {
        int u=eg[i];
        if(u!=fa && !Isc[u]) Cal_Dist(u,v,precost+W[i]);
    }
}
int Cal_Ans(int dis[],int Siz)
{
    int res=0;
    sort(dis,dis+Siz);
    for(int i=0;i<Siz;++i) {
        res+=upper_bound(dis+1+i,dis+Siz,K-dis[i])-(dis+1+i);
    }
    return res;
}
void solve(int v)
{
    Cal_Size(v,-1);
    int cv=Find_Centroid(v,-1,siz[v]).sec;
    Isc[cv]=true;
 
    for(int i=head[cv];i;i=nxt[i]) {
        int u=eg[i];
        if(!Isc[u]) solve(u);
    }
 
    allsiz=0;all[allsiz++]=0;
    for(int i=head[cv];i;i=nxt[i]) {
        int u=eg[i];
        if(Isc[u]) continue;
        parsiz=0;
        Cal_Dist(u,cv,W[i]);
        ans-=Cal_Ans(par,parsiz);
        memcpy(all+allsiz,par,parsiz*(sizeof(par[0])));
        allsiz+=parsiz;
    }
    ans+=Cal_Ans(all,allsiz);
    Isc[cv]=0;
}
int main()
{
    n=readInt();
    int u,v,w;
    for(int i=1;i<=n-1;i++) {
        u=readInt(),v=readInt(),w=readInt();
        addedge(u,v,w);
    }
    K=readInt();
    solve(1);
    printf("%d\n",ans);
    return 0;
}