latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2017年3月7日 星期二

[ POJ 1741 ] Tree

題目:
http://poj.org/problem?id=1741

解法:
樹分治,找出重心後,算出通過重心且長度$\leq k$的路徑有幾個,因為我是所有路徑一起算的,所以還要扣掉在同一個子樹的路徑,算路徑會花$\ord{n log n}$,樹分治深度最多$\ord{log n}$,因此總複雜度是$\ord{n log^2 n}$

code:

 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
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
int n,k;
vector<pair<int,int> >g[MAXN];
int size[MAXN];
bool vis[MAXN];
inline void init(){
    for(int i=0;i<=n;++i){
        g[i].clear();
        vis[i]=0;
    }
}
void get_dis(vector<int> &dis,int u,int pa,int d){
    dis.push_back(d);
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first,w=g[u][i].second;
        if(v!=pa&&!vis[v])get_dis(dis,v,u,d+w);
    }
}
vector<int> dis;//這東西如果放在函數裡會TLE
int cal(int u,int d){
    dis.clear();
    get_dis(dis,u,-1,d);
    sort(dis.begin(),dis.end());
    int l=0,r=dis.size()-1,res=0;
    while(l<r){
        while(l<r&&dis[l]+dis[r]>k)--r;
        res+=r-(l++);
    }
    return res;
}
pair<int,int> tree_centroid(int u,int pa,const int sz){
    size[u]=1;//找樹重心,second是重心
    pair<int,int> res(INT_MAX,-1);
    int ma=0;
    for(size_t i=0;i<g[u].size();++i){
        int v=g[u][i].first;
        if(v==pa||vis[v])continue;
        res=min(res,tree_centroid(v,u,sz));
        size[u]+=size[v];
        ma=max(ma,size[v]);
    }
    ma=max(ma,sz-size[u]);
    return min(res,make_pair(ma,u));
}
int tree_DC(int u,int sz){
    int center=tree_centroid(u,-1,sz).second;
    int ans=cal(center,0);
    vis[center]=1;
    for(size_t i=0;i<g[center].size();++i){
        int v=g[center][i].first,w=g[center][i].second;
        if(vis[v])continue;
        ans-=cal(v,w);
        if(size[v]>size[center])
            size[v]=sz-size[center];
        ans+=tree_DC(v,size[v]);
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&k),n||k){
        init();
        for(int i=1;i<n;++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
        }
        printf("%d\n",tree_DC(1,n));
    }
    return 0;
}