树的重心点分治

最近学了下点分治

说道点分治就得先说到树的重心

树的重心的定义是：最大的子树最小的节点。

为什么要找树的重心呢

因为找到树的重心把他变成根以后，最大的子树的大小不超过n/2，否则如果超过n/2将该子树的根作为重心将会更优。

这样可以保证递归的层数不超过logn层，同时保证每个点最多被计算logn次。

那么如何找重心呢

根据定义，我们不妨维护一下两个数组sz[]和mx[]表示以r为根的子树大小和无根树中的最大子树大小，那么mx最小的那个节点就是重心。

有两种写法一种是

void getroot(int x,int fa)
{
    son[x]=1;f[x]=0;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa||vis[e[i].to])continue;
        getroot(e[i].to,x);
        son[x]+=son[e[i].to];
        f[x]=max(f[x],son[e[i].to]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root])root=x;
}

另一种写法是用两个函数

void dfs_size(int x,int fa) {
    sz[x]=1;
    mx[x]=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_size(p->to,x);
        sz[x] += sz[p->to];
        maxit(mx[x],sz[p->to]);
    }
}

int root=0;
void dfs_root(int r,int x,int fa) {
    maxit(mx[x],sz[r]-sz[x]);
    if(mx[x]<mx[root]) root=x;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_root(r,p->to,x);
    }
}

我采用的后者，因为太弱了第一种一开始没看懂。

我一直觉得只用dfs一次就可以把每个子树的重心找到，后来发现每一棵子树都要找一次orz感觉复杂度一下就上去了

然后有两道找树的重心的题

poj1655

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cstring>
 6 
 7 using namespace std;
 8 
 9 const int Maxn=20000+10,INF=0x7fffffff;
10 
11 struct Edge{
12     int to;
13     Edge*next;
14     Edge(int to=0,Edge* next=0):to(to),next(next){}
15 }pool[Maxn*2],*fir[Maxn],*pis=pool;
16 
17 void AddEdge(int from,int to){
18     *pis=Edge(to,fir[from]);fir[from]=pis++;
19     *pis=Edge(from,fir[to]);fir[to]=pis++;
20 }
21 
22 int sz[Maxn],mx[Maxn];
23 void dfs_size(int x,int fa) {
24     sz[x]=1;
25     mx[x]=0;
26     for(Edge*p=fir[x];p;p=p->next) {
27         if(p->to==fa) continue;
28         dfs_size(p->to,x);
29         sz[x] += sz[p->to];
30         mx[x]=max(mx[x],sz[p->to]);
31     }
32 }
33 
34 int root;
35 
36 void dfs_root(int r,int x,int fa) {
37     mx[x]=max(mx[x],sz[r]-sz[x]);
38     if(mx[root]>mx[x]) root=x;
39     for(Edge*p=fir[x];p;p=p->next) {
40         if(p->to==fa) continue;
41         dfs_root(r,p->to,x);
42     }
43 }
44 
45 int n;
46 void init() {
47     root=0;
48     mx[0]=INF;
49     pis=pool;
50     memset(fir,0,sizeof fir);
51     for(int i=1;i<n;i++) {
52         int u,v;
53         scanf("%d%d",&u,&v);
54         AddEdge(u,v);
55     }
56 }
57 
58 int main() {
59 #ifdef DEBUG
60     freopen("in.txt","r",stdin);
61     freopen("out.txt","w",stdout);
62 #endif
63     
64     int T;
65     for(scanf("%d",&T);T--;) {
66         scanf("%d",&n);
67         init();
68         dfs_size(1,0);
69         dfs_root(1,1,0);
70         printf("%d %d
",root,mx[root]);
71     }
72     
73     return 0;
74 }

View Code

poj3170

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<cstring>
 6 
 7 using namespace std;
 8 
 9 const int Maxn=50000+10,INF=0x7fffffff;
10 
11 struct Edge{
12     int to;
13     Edge*next;
14     Edge(int to=0,Edge* next=0):to(to),next(next){}
15 }pool[Maxn*2],*fir[Maxn],*pis=pool;
16 
17 void AddEdge(int from,int to){
18     *pis=Edge(to,fir[from]);fir[from]=pis++;
19     *pis=Edge(from,fir[to]);fir[to]=pis++;
20 }
21 
22 int sz[Maxn],mx[Maxn];
23 void dfs_size(int x,int fa) {
24     sz[x]=1;
25     mx[x]=0;
26     for(Edge*p=fir[x];p;p=p->next) {
27         if(p->to==fa) continue;
28         dfs_size(p->to,x);
29         sz[x] += sz[p->to];
30         mx[x]=max(mx[x],sz[p->to]);
31     }
32 }
33 
34 int root;
35 int ans[Maxn],tot;
36 
37 void dfs_root(int r,int x,int fa) {
38     mx[x]=max(mx[x],sz[r]-sz[x]);
39     if(mx[root]>mx[x]) ans[tot=1]=root=x;
40     else if(mx[root]==mx[x]) ans[++tot]=x;
41     for(Edge*p=fir[x];p;p=p->next) {
42         if(p->to==fa) continue;
43         dfs_root(r,p->to,x);
44     }
45 }
46 
47 int n;
48 void init() {
49     root=0;
50     mx[0]=INF;
51     pis=pool;
52     memset(fir,0,sizeof fir);
53     for(int i=1;i<n;i++) {
54         int u,v;
55         scanf("%d%d",&u,&v);
56         AddEdge(u,v);
57     }
58 }
59 
60 int main() {
61 #ifdef DEBUG
62     freopen("in.txt","r",stdin);
63     freopen("out.txt","w",stdout);
64 #endif
65     
66     for(;~scanf("%d",&n);) {
67         init();
68         dfs_size(1,0);
69         dfs_root(1,1,0);
70         sort(ans+1,ans+tot+1);
71         for(int i=1;i<=tot;i++) {
72             printf("%d%c",ans[i],i==n?'
':' ');
73         }
74     }
75     
76     return 0;
77 }

View Code

之后做了几道hzwer上的点分治，贴下代码QuQ

bzoj2152

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>

using namespace std;

const int Maxn=20005,INF=0x7fffffff;
struct Edge{
    int to,v;
    Edge*next;
    Edge(int to=0,int v=0,Edge*next=NULL):to(to),v(v),next(next){
        
    }
}pool[Maxn*2],*fir[Maxn],*pis;

void AddEdge(int from,int to,int v){
    *pis=Edge(to,v,fir[from]);fir[from]=pis++;
    *pis=Edge(from,v,fir[to]);fir[to]=pis++;
}

int sz[Maxn],mx[Maxn];
int vis[Maxn],clk;
void dfs_size(int x,int fa) {
    sz[x]=1;
    mx[x]=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_size(p->to,x);
        sz[x] += sz[p->to];
        mx[x] = max(mx[x],sz[p->to]);
    }
}

int root=0;
void dfs_root(int r,int x,int fa) {
    mx[x] = max(mx[x],sz[r]-sz[x]);
    if(mx[root]>mx[x]) root=x;
    
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_root(r,p->to,x);
    }
}

int num[3];
void dfs_dis(int x,int d,int fa) {
    num[d]++;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_dis(p->to,(d+p->v)%3,x);
    }
}

int k;
int calc(int x,int d) {
    int ret=0;
    memset(num,0,sizeof num);
    dfs_dis(x,d,0);
    ret += num[0]*(num[0]-1)/2;
    ret += num[1]*num[2];
    return ret;
}
int ans;
void dfs(int x) {
    dfs_size(x,0);
    root=0;
    dfs_root(x,x,0);
    vis[root]=clk;
    ans += calc(root,0);
    for(Edge*p=fir[root];p;p=p->next) {
        if(vis[p->to]==clk) continue;
        ans -= calc(p->to,p->v);
        dfs(p->to);
    }
}
int n;
void init() {
    memset(mx,0,sizeof mx);
    mx[0]=INF;
    ans=0;
    ++clk;
    memset(fir,0,sizeof fir);
    pis=pool;
    int u,v,w;
    for(int i=1;i<n;i++) {
        scanf("%d%d%d",&u,&v,&w);
        AddEdge(u,v,w%3);
    }
}

int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
#ifdef DEBUG
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    
    for(;scanf("%d",&n)==1 && n;) {
        init();
        dfs(1);
        int a=ans*2+n,b=n*n;
        int g=gcd(a,b);
        printf("%d/%d
",a/g,b/g);
    }
    
    return 0;
}

View Code

bzoj3697

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>

using namespace std;
typedef long long ll;
const int Maxn=100005,INF=0x3f3f3f3f;
struct Edge{
    int to,v;
    Edge*next;
    Edge(int to=0,int v=0,Edge*next=NULL):to(to),v(v),next(next){
        
    }
}pool[Maxn*2],*fir[Maxn],*pis;

void AddEdge(int from,int to,int v){
    *pis=Edge(to,v,fir[from]);fir[from]=pis++;
    *pis=Edge(from,v,fir[to]);fir[to]=pis++;
}

int sz[Maxn],mx[Maxn];
int vis[Maxn],clk;
void dfs_size(int x,int fa) {
    sz[x]=1;
    mx[x]=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_size(p->to,x);
        sz[x] += sz[p->to];
        mx[x] = max(mx[x],sz[p->to]);
    }
}

int root=0;
void dfs_root(int r,int x,int fa) {
    mx[x] = max(mx[x],sz[r]-sz[x]);
    if(mx[root]>mx[x]) root=x;
    
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_root(r,p->to,x);
    }
}

int n;
int f[Maxn*2+10][2];
int g[Maxn*2+10][2];
int t[Maxn*2+10];
int max_deep;
#define f(a,b) f[a+n][b]
#define g(a,b) g[a+n][b]
#define t(a) t[a+n]
void dfs_dis(int x,int d,int fa) {
    max_deep=max(max_deep,abs(d));
    if(t(d)++) g(d,1)++;
    else g(d,0)++;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_dis(p->to,d+p->v,x);
    }
    t(d)--;
}

int k;
ll ans;

void dfs(int x) {
    int mx=0;
    dfs_size(x,0);
    root=0;
    dfs_root(x,x,0);
    vis[root]=clk;
    f(0,0)=1;
    for(Edge*p=fir[root];p;p=p->next) {
        if(vis[p->to]==clk) continue;
        max_deep=0;
        dfs_dis(p->to,p->v,root);
        mx=max(max_deep,mx);
        ans += 1ll*(f(0,0)-1)*g(0,0);
        for(int i = -max_deep;i <= max_deep;i++) {
            ans += 1ll*f(i,0)*g(-i,1) + f(i,1)*g(-i,0) + f(i,1)*g(-i,1);
        }
        for(int i = -max_deep;i <= max_deep;i++) {
            f(i,0) += g(i,0);
            f(i,1) += g(i,1);
            g(i,0) = g(i,1) = 0;
        }
    }
    for(int i=-mx;i<=mx;i++) f(i,0)=f(i,1)=0;
    for(Edge*p=fir[root];p;p=p->next) {
        if(vis[p->to]!=clk) dfs(p->to);
    }
}
void init() {
    max_deep=0;
    memset(mx,0,sizeof mx);
    mx[0]=INF;
    ans=0;
    ++clk;
    memset(fir,0,sizeof fir);
    pis=pool;
    int u,v,w;
    for(int i=1;i<n;i++) {
        scanf("%d%d%d",&u,&v,&w);
        AddEdge(u,v,w==1?1:-1);
    }
}

int main(){
#ifdef DEBUG
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    
    for(;scanf("%d",&n)==1;) {
        init();
        dfs(1);
        cout<<ans<<endl;
    }
    
    return 0;
}

View Code

bzoj1758

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>

using namespace std;
typedef long long ll;
const int Maxn=100005,INF=0x3f3f3f3f;
const double eps=1e-7;
int U,L;
struct Edge{
    int to,v;
    Edge*next;
    Edge(int to=0,int v=0,Edge*next=NULL):to(to),v(v),next(next){
        
    }
}pool[Maxn*2],*fir[Maxn],*pis;

void AddEdge(int from,int to,int v){
    *pis=Edge(to,v,fir[from]);fir[from]=pis++;
    *pis=Edge(from,v,fir[to]);fir[to]=pis++;
}

template<typename Q> void maxit(Q&x,const Q&y) {
    if(x<y) x=y;
}

int sz[Maxn],mx[Maxn];
int vis[Maxn],clk=0;
void dfs_size(int x,int fa) {
    sz[x]=1;
    mx[x]=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_size(p->to,x);
        sz[x] += sz[p->to];
        maxit(mx[x],sz[p->to]);
    }
}

int root=0;
void dfs_root(int r,int x,int fa) {
    maxit(mx[x],sz[r]-sz[x]);
    if(mx[x]<mx[root]) root=x;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_root(r,p->to,x);
    }
}

int dep[Maxn],fa[Maxn];
double dis[Maxn],M,ans=0,lim;
double f[Maxn];

bool check(int x) {
    int up=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(vis[p->to]==clk) continue;
//        if(f[0]!=0) exit(1);
        static int q[Maxn],ql,qr;
        ql=qr=0;
        
        fa[x]=0;
        dis[x]=dep[x]=0;
        q[++qr]=p->to;
        fa[p->to]=x;
        dep[p->to]=1;
        dis[p->to]=p->v-M;
        
        for(int u;ql<qr;) {
            u=q[++ql];
            for(Edge*p=fir[u];p;p=p->next) {
                if(p->to!=fa[u] && vis[p->to]!=clk) {
                    q[++qr] = p->to;
                    fa[p->to]=u;
                    dep[p->to]=dep[u]+1;
                    dis[p->to]=dis[u]+p->v-M;
                }
            }
        }
        for(int i=up+1;i<=dep[q[qr]];i++) f[i]= -INF;
        static int mq[Maxn],ml,mr;
        ml=mr=0;int now=up;
        for(int i=1;i<=qr;i++) {
            int x=q[i];
            for(;dep[x]+now>=L&&now>=0;now--) {
                for(;ml<mr && f[mq[mr]] < f[now];mr--);
                mq[++mr] = now;
            }
            for(;dep[x]+mq[ml+1]>U && ml<mr;ml++);
            if(ml<mr && f[mq[ml+1]] + dis[x]>=-eps) return 1;
        }
        
        for(int i=1;i<=qr;i++) {
            maxit(f[dep[q[i]]],dis[q[i]]);
        }
        maxit(up,dep[q[qr]]);
    }
    return 0;
}

void dfs(int x) {
    dfs_size(x,0);
    dfs_root(x,x,root=0);
    vis[root]=clk;
    
    double l=ans,r=lim;
    for(;r-l>eps;) {
        M=l+(r-l)/2;
        if(check(root)) l=M;
        else r=M;
    }
    ans=l;
    
    for(Edge*p=fir[root];p;p=p->next) {
        if(!vis[p->to]) dfs(p->to);
    }
}

int n;
void init() {
    mx[0]=INF;
    ++clk;
    memset(fir,0,sizeof fir);
    pis=pool;
    
    scanf("%d%d%d",&n,&L,&U);
    for(int i=1;i<n;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        AddEdge(u,v,w);
        maxit(lim,(double)w);
    }
}

int main(){
#ifdef DEBUG
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    
    init();
    dfs(1);
    printf("%.3lf
",ans);
    
    return 0;
}

View Code

bzoj3784

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #include<queue>
  7 
  8 using namespace std;
  9 
 10 const int Maxn=50010,logn=21;
 11 const int nlogn=800000;
 12 const int INF=0x3f3f3f3f;
 13 struct Edge{
 14     int to,v;
 15     Edge*next;
 16     Edge(int to=0,Edge*next=0,int v=0):to(to),v(v),next(next){}
 17 }pool[Maxn*2],*pis=pool,*fir[Maxn];
 18 
 19 void AddEdge(int from,int to,int v) {
 20     *pis=Edge(to,fir[from],v);fir[from]=pis++;
 21     *pis=Edge(from,fir[to],v);fir[to]=pis++;
 22 }
 23 
 24 template<typename Q>void maxit(Q&x,const Q&y) {
 25     if(x<y) x=y;
 26 }
 27 int sz[Maxn],mx[Maxn];
 28 bool vis[Maxn];
 29 void dfs_size(int x,int fa) {
 30     sz[x]=1;
 31     mx[x]=0;
 32     for(Edge*p=fir[x];p;p=p->next) {
 33         if(vis[p->to] || p->to==fa) continue;
 34         dfs_size(p->to,x);
 35         sz[x] += sz[p->to];
 36         maxit(mx[x],sz[p->to]);
 37     }
 38 }
 39 
 40 int root=0;
 41 void dfs_root(int r,int x,int fa) {
 42     maxit(mx[x],sz[r]-sz[x]);
 43     if(mx[x]<mx[root]) root=x;
 44     for(Edge*p=fir[x];p;p=p->next) {
 45         if(vis[p->to] || p->to==fa) continue;
 46         dfs_root(r,p->to,x);
 47     }
 48 }
 49 
 50 int tot;
 51 struct Data2 {
 52     int v,pos;
 53     Data2(int v=0,int pos=0):v(v),pos(pos) {}
 54     Data2 operator + (const Data2&rhs) const {
 55         return v>rhs.v?*this:rhs;
 56     }
 57 }st[nlogn][logn];
 58 
 59 void dfs_dis(int x,int d,int fa) {
 60     ++tot;
 61     st[tot][0] = Data2(d,tot);
 62     for(Edge*p=fir[x];p;p=p->next) {
 63         if(vis[p->to] || p->to==fa) continue;
 64         dfs_dis(p->to,d+p->v,x);
 65     }
 66 }
 67 
 68 int L[nlogn],R[nlogn];
 69 
 70 struct Data {
 71     int id,l,r,v,pos;
 72     bool operator < (const Data& rhs) const {
 73         return v<rhs.v;
 74     }
 75     Data(int id,int l,int r,int v,int pos):id(id),l(l),r(r),v(v),pos(pos) {}
 76     Data() {}
 77 };
 78 
 79 priority_queue<Data> q;
 80 
 81 void st_init() {
 82     for(int i=0;i<=tot;i++) {
 83         for(int j=1;(i+(1<<(j-1)))<=tot;j++) {
 84             st[i][j] = st[i][j-1] + st[i+(1<<(j-1))][j-1];
 85         }
 86     }
 87 }
 88 
 89 Data2 st_query(int l,int r) {
 90     int k=0;
 91     while( ( 1<<(k+1) ) <=r-l+1)k++;//如果2^(k+1)<=R-L+1,则k还可以+1
 92     return st[l][k]+st[r-(1<<k)+1][k];
 93 }
 94 
 95 void dfs(int x) {
 96     dfs_size(x,0);
 97     dfs_root(x,x,root=0);
 98     vis[x=root]=1;
 99     
100     int s=++tot;
101     st[tot][0]=Data2(0,tot);
102     for(Edge*p=fir[x];p;p=p->next) {
103         if(vis[p->to]) continue;
104         int t=tot;
105         dfs_dis(p->to,p->v,x);
106         for(int i=t+1;i<=tot;i++) {
107             L[i]=s;
108             R[i]=t;
109         }
110     }
111     for(Edge*p=fir[x];p;p=p->next) {
112         if(!vis[p->to]) dfs(p->to);
113     }
114 }
115 
116 int n,m;
117 
118 void init() {
119     mx[0]=INF;
120     scanf("%d%d",&n,&m);
121     for(int i=1;i<n;i++) {
122         int u,v,w;
123         scanf("%d%d%d",&u,&v,&w);
124         AddEdge(u,v,w);
125     }
126 }
127 
128 //#define dout printf
129 void work() {
130     dfs(1);
131     st_init();
132     
133     /*
134     dout("tot=%d
",tot);
135     for(int i=1;i<=tot;i++) {
136         dout("(%d,%d,%d)
",st[i][0].v,L[i],R[i]);
137     }
138     dout("------------------
");
139     for(int i=1;i<=tot;i++) {
140         for(int j=0;(1<<j)<=tot;j++) {
141             dout("st[%d][%d]=(%d,%d)",i,j,st[i][j].v,st[i][j].pos);
142         }
143         dout("
");
144     }*/
145     
146     for(int i=1;i<=tot;i++) {
147 //        if(L[i]==R[i] && L[i]==0) continue;
148         Data2 tmp=st_query(L[i],R[i]);
149         q.push(Data(i, L[i],R[i], tmp.v+st[i][0].v, tmp.pos));
150     }
151     for(Data s;m--;) {
152         s=q.top();q.pop();
153         printf("%d
",s.v);
154         if(s.l!=s.pos) {
155             Data2 t=st_query(s.l,s.pos-1);
156             q.push(Data(s.id, s.l, s.pos-1, t.v+st[s.id][0].v, t.pos));
157         }
158         if(s.r!=s.pos) {
159             Data2 t=st_query(s.pos+1,s.r);
160             q.push(Data(s.id, s.pos+1, s.r, t.v+st[s.id][0].v, t.pos));
161         }
162     }
163 }
164 
165 
166 int main() {
167 #ifdef DEBUG
168     freopen("in.txt","r",stdin);
169 //    freopen("out.txt","w",stdout);
170 #endif
171     
172     init();
173     work(); 
174     
175     return 0;
176 }

View Code

bzoj4016

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #include<vector>
  7 #include<queue>
  8 
  9 using namespace std;
 10 
 11 const int Maxn=30000+10,Maxm=60000+10,INF=0x3f3f3f3f;
 12 typedef pair<int,int> pii;
 13 vector<pii>e[Maxn];
 14 
 15 void AddEdge(int from,int to,int w) {
 16     e[from].push_back(make_pair(to,w));
 17     e[to].push_back(make_pair(from,w));
 18 }
 19 struct Edge{
 20     int to;
 21     Edge*next;
 22     int w;
 23     Edge(int to=0,Edge*next=0,int w=0):to(to),next(next),w(w) {}
 24 }pool[Maxn*2+Maxm*2],*pis=pool,*fir0[Maxn],*fir[Maxn];
 25 
 26 void Add(Edge* fir[],int from,int to,int w) {
 27     *pis=Edge(to,fir[from],w);fir[from]=pis++;
 28 //    *pis=Edge(from,fir[to],w);fir[to]=pis++;
 29 }
 30 
 31 priority_queue<pii,vector<pii>,greater<pii> > q;
 32 int d[Maxn];
 33 bool vis[Maxn];
 34 void Dijkstra() {
 35     memset(d,0x3f,sizeof d);
 36     q.push(make_pair(0,1));
 37     d[1]=0;
 38     for(pii tmp;!q.empty();) {
 39         tmp=q.top();q.pop();
 40         int x=tmp.second;
 41         if(vis[x]) continue;
 42         vis[x]=1;
 43         for(Edge*p=fir0[x];p;p=p->next) {
 44             if(d[x]+p->w < d[p->to]) {
 45                 d[p->to] = d[x]+p->w;
 46                 q.push(make_pair(d[p->to],p->to));
 47             }
 48         }
 49     }
 50 }
 51 
 52 void dfs_path(int x) {
 53     vis[x]=1;
 54     for(Edge*p=fir0[x];p;p=p->next) {
 55         if(!vis[p->to] && d[x]+p->w==d[p->to]) {
 56             Add(fir,x,p->to,p->w);
 57             Add(fir,p->to,x,p->w);
 58             dfs_path(p->to);
 59         }
 60     }
 61 }
 62         
 63 
 64 int sz[Maxn],mx[Maxn];
 65 int root=0;
 66 
 67 template<typename Q> void maxit(Q&x,Q y) {
 68     if(x<y) x=y;
 69 }
 70 
 71 void dfs_size(int x,int fa) {
 72     sz[x]=1;
 73     mx[x]=0;
 74     for(Edge*p=fir[x];p;p=p->next) {
 75         if(vis[p->to] || p->to==fa) continue;
 76         dfs_size(p->to,x);
 77         sz[x] += sz[p->to];
 78         maxit(mx[x],sz[p->to]);
 79     }
 80 }
 81 
 82 void dfs_root(int r,int x,int fa) {
 83     maxit(mx[x],sz[r]-sz[x]);
 84     if(mx[x]<mx[root]) root=x;
 85     for(Edge*p=fir[x];p;p=p->next) {
 86         if(p->to==fa || vis[p->to]) continue;
 87         dfs_root(r,p->to,x);
 88     }
 89 }
 90 
 91 int max_deep,md;
 92 int f[Maxn][2],g[Maxn][2];//[i][0] i条的最大长度 [1]方案数 
 93 int K;
 94 void dfs_dis(int x,int dep,int d,int fa) {
 95     if(dep>K) return;
 96     maxit(max_deep,dep);
 97     maxit(md,dep);
 98     if(g[dep][0]<d) g[dep][0]=d, g[dep][1]=1;
 99     else if(g[dep][0]==d) g[dep][1]++;
100     
101     for(Edge*p=fir[x];p;p=p->next) {
102         if(p->to==fa || vis[p->to]) continue;
103         dfs_dis(p->to,dep+1,d+p->w,x);
104     }
105 }
106 
107 int ans1=0,ans2;
108 void dfs(int x) {
109     dfs_size(x,0);
110     dfs_root(x,x,root=0);
111     vis[x=root]=1;
112     
113     max_deep=0;
114     g[0][0]=f[0][0]=0;
115     g[0][1]=f[0][1]=1;
116     
117     for(Edge*p=fir[x];p;p=p->next) {
118         if(vis[p->to]) continue;
119         md=0;
120         dfs_dis(p->to,1,p->w,x);
121         
122         for(int i=1;i<=md;i++) {
123             if(g[i][0] + f[K-i][0]>ans1) 
124                 ans1=g[i][0] + f[K-i][0],ans2=0; 
125             if(g[i][0] + f[K-i][0]==ans1) 
126                 ans2 += g[i][1] * f[K-i][1];
127         }
128         for(int i=1;i<=md;i++) {
129             if(f[i][0]<g[i][0]) f[i][0]=g[i][0], f[i][1]=0;
130             if(f[i][0]==g[i][0]) f[i][1] += g[i][1]; 
131             g[i][0]=-INF;
132         }
133     }
134     for(int i=1;i<=max_deep;i++) f[i][0]=0;
135     for(Edge*p=fir[x];p;p=p->next) {
136         if(!vis[p->to]) dfs(p->to);
137     }
138 }
139 
140 int n,m;
141 
142 void init() {
143     scanf("%d%d%d",&n,&m,&K); K--;
144     int u,v,w;
145     for(int i=1;i<=m;i++) {
146         scanf("%d%d%d",&u,&v,&w);
147         AddEdge(u,v,w);
148     }
149     for(int i=1;i<=n;i++) {
150         sort(e[i].begin(),e[i].end());
151         for(int j=e[i].size()-1;j>=0;j--) {
152             Add(fir0, i, e[i][j].first, e[i][j].second);
153         }
154     }
155     mx[0]=INF;
156 //    for(int i=0;i<Maxn;i++) f[i][0]=g[i][0]=-INF;
157 }
158 
159 int main() {
160 #ifdef DEBUG
161     freopen("in.txt","r",stdin);
162     freopen("out.txt","w",stdout);
163 #endif
164     
165     init();
166     memset(vis,0,sizeof vis);
167     Dijkstra();
168     memset(vis,0,sizeof vis);
169     dfs_path(1);
170     memset(vis,0,sizeof vis);
171     dfs(1);
172     printf("%d %d
",ans1,ans2);
173     
174     return 0;
175 }

View Code

bzoj1468

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 
  9 const int Maxn=40010,INF=0x3f3f3f3f;
 10 
 11 struct Edge{
 12     int to;
 13     Edge*next;
 14     int w;
 15     Edge(int to=0,Edge*next=0,int w=0):to(to),next(next),w(w) {}
 16 }pool[Maxn*2],*fir[Maxn],*pis=pool;
 17 
 18 void AddEdge(int from,int to,int w) {
 19     *pis=Edge(to,fir[from],w);fir[from]=pis++;
 20     *pis=Edge(from,fir[to],w);fir[to]=pis++;
 21 }
 22 
 23 struct Node{
 24     int s,v,r;
 25     Node*ch[2];
 26     Node(int v=0):v(v){r=rand(),s=1;ch[0]=ch[1]=0;}
 27     void maintain() {
 28         s=1;
 29         if(ch[0]) s += ch[0]->s;
 30         if(ch[1]) s += ch[1]->s;
 31     }
 32     int cmp(int k) {
 33         if(k==v) return -1;
 34         return k<v?0:1;
 35     }
 36 }npool[Maxn],*g,*f,*nps=npool;
 37 
 38 void rotate(Node*&o,int d) {
 39     Node*t=o->ch[d];
 40     o->ch[d]=t->ch[d^1];
 41     t->ch[d^1]=o;
 42     o->maintain();
 43     (o=t)->maintain();
 44 }
 45 
 46 void insert(Node*&o,int x) {
 47     if(!o) {
 48         o=nps++;
 49         *o=Node(x);
 50         return;
 51     }
 52     int d=o->cmp(x);
 53     if(d==-1) d=0;
 54     insert(o->ch[d],x);
 55     if(o->ch[d]->r < o->r) rotate(o,d);
 56     o->maintain();
 57 }
 58 
 59 void remove(Node*&o,int x) {
 60     if(!o) return;
 61     int d=o->cmp(x);
 62     if(d==-1) {
 63         if(!o->ch[0]) o=o->ch[1];
 64         else if(!o->ch[1]) o=o->ch[0];
 65         else {
 66             int d2=o->ch[0]->r < o->ch[1]->r ?0:1;
 67             rotate(o,d2);
 68             remove(o->ch[d2^1],x);
 69         }
 70     }else remove(o->ch[d],x);
 71     if(o) o->maintain();
 72 }
 73 
 74 int rank(Node*o,int x) {
 75     int ans=0;
 76     for(int d;o;o=o->ch[d]) {
 77         d=o->cmp(x);
 78         if(d==-1) d=0;
 79         int s=1;
 80         if(o->ch[0]) s+=o->ch[0]->s;
 81         if(d==1) ans += s;
 82     }
 83     return ans+1;
 84 }
 85 
 86 Node*kth(Node*o,int k) {
 87     for(int d;o;o=o->ch[d]) {
 88         int s=o->ch[0]?o->ch[0]->s:0;
 89         if(k==s+1) return o;
 90         if(k>s) k-= s+1,d=1;
 91         else d=0;
 92     }
 93     return NULL;
 94 }
 95 
 96 Node*Pre(Node*o,int x) {
 97     Node*ans=NULL;
 98     for(int d;o;o=o->ch[d]) {
 99         d=o->cmp(x);
100         if(d==-1) d=0;
101         if(d==1) ans=o;
102     }
103     return ans;
104 }
105 
106 Node*Sub(Node*o,int x) {
107     Node*ans=NULL;
108     for(int d;o;o=o->ch[d]) {
109         d=o->cmp(x);
110         if(d==-1) d=1;
111         if(d==0) ans=o;
112     }
113     return ans;
114 }
115 
116 template<typename Q> void maxit(Q&x,const Q&y) {
117     if(x<y) x=y;
118 }
119 int mx[Maxn],sz[Maxn];
120 bool vis[Maxn];
121 void dfs_size(int x,int fa) {
122     sz[x] = 1;
123     mx[x] = 0;
124     for(Edge*p=fir[x];p;p=p->next) {
125         if(vis[p->to] || p->to==fa) continue;
126         dfs_size(p->to,x);
127         sz[x] += sz[p->to];
128     }
129 }
130 
131 int root=0;
132 void dfs_root(int r,int x,int fa) {
133     maxit(mx[x],sz[r]-sz[x]);
134     if(mx[x]<mx[root]) root=x;
135     for(Edge*p=fir[x];p;p=p->next) {
136         if(vis[p->to] || p->to==fa) continue;
137         dfs_root(r,p->to,x);
138     }
139 }
140 
141 int seq[Maxn],tot;
142 int K;
143 void dfs_dis(int x,int d,int fa) {
144     if(d>K) return;
145     seq[++tot]=d;
146     for(Edge*p=fir[x];p;p=p->next) if(!vis[p->to] && p->to!=fa) {
147         dfs_dis(p->to,d+p->w,x);
148     }
149 }
150 
151 int ans=0;
152 
153 void dfs(int x) {
154     dfs_size(x,0);
155     dfs_root(x,x,root=0);
156     vis[x=root]=1;
157     
158     nps=npool;
159     f=NULL;
160     insert(f,0);
161     
162     for(Edge*p=fir[x];p;p=p->next) if(!vis[p->to]) {
163         tot=0;
164         dfs_dis(p->to,p->w,x);
165         for(int i=1;i<=tot;i++) {
166             ans += rank(f,K-seq[i]+1)-1;
167         }
168         for(int i=1;i<=tot;i++) {
169             insert(f,seq[i]);
170         }
171     }
172     
173     for(Edge*p=fir[x];p;p=p->next) if(!vis[p->to]) {
174         dfs(p->to);
175     }
176 }
177 
178 void init() {
179     int n;
180     scanf("%d",&n);
181     for(int i=1;i<n;i++) {
182         int u,v,w;
183         scanf("%d%d%d",&u,&v,&w);
184         AddEdge(u,v,w);
185     }
186     scanf("%d",&K);
187     mx[0]=INF;
188 }
189 
190 int main() {
191 #ifdef DEBUG
192     freopen("in.txt","r",stdin);
193 //    freopen("out.txt","w",stdout);
194 #endif
195     
196     init();
197     dfs(1);
198     printf("%d
",ans);
199     
200     return 0;
201 }

View Code

poj1741

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>

using namespace std;

const int Maxn=10005,INF=0x7fffffff;
struct Edge{
    int to,v;
    Edge*next;
    Edge(int to=0,int v=0,Edge*next=NULL):to(to),v(v),next(next){
        
    }
}pool[Maxn*2],*fir[Maxn],*pis;

void AddEdge(int from,int to,int v){
    *pis=Edge(to,v,fir[from]);fir[from]=pis++;
    *pis=Edge(from,v,fir[to]);fir[to]=pis++;
}

int sz[Maxn],mx[Maxn];
int vis[Maxn],clk;
void dfs_size(int x,int fa) {
    sz[x]=1;
    mx[x]=0;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_size(p->to,x);
        sz[x] += sz[p->to];
        mx[x] = max(mx[x],sz[p->to]);
    }
}

int root=0;
void dfs_root(int r,int x,int fa) {
    mx[x] = max(mx[x],sz[r]-sz[x]);
    if(mx[root]>mx[x]) root=x;
    
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_root(r,p->to,x);
    }
}

int ds[Maxn],tot;
void dfs_dis(int x,int d,int fa) {
    ds[++tot]=d;
    for(Edge*p=fir[x];p;p=p->next) {
        if(p->to==fa || vis[p->to]==clk) continue;
        dfs_dis(p->to,d+p->v,x);
    }
}

int k;
int calc(int x,int d) {
    int ret=0;
    tot=0;
    dfs_dis(x,d,0);
    sort(ds+1,ds+tot+1);
    int l=1,r=tot;
    for(;l<r;l++) {
        for(;ds[l]+ds[r]>k && l<r; r--);
        ret+=r-l;
    }
    return ret;
}
        

int ans;
void dfs(int x) {
    dfs_size(x,0);
    root=0;
    dfs_root(x,x,0);
    vis[root]=clk;
    ans += calc(root,0);
    for(Edge*p=fir[root];p;p=p->next) {
        if(vis[p->to]==clk) continue;
        ans -= calc(p->to,p->v);
        dfs(p->to);
    }
}
int n;
void init() {
    memset(mx,0,sizeof mx);
    mx[0]=INF;
    ans=0;
    ++clk;
    memset(fir,0,sizeof fir);
    pis=pool;
    int u,v,w;
    for(int i=1;i<n;i++) {
        scanf("%d%d%d",&u,&v,&w);
        AddEdge(u,v,w);
    }
}

int main(){
#ifdef DEBUG
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    
    for(;scanf("%d%d",&n,&k)==2 && n &&k;) {
        init();
        dfs(1);
        printf("%d
",ans);
    }
    
    return 0;
}

View Code

bzoj2599

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<vector>
  8 
  9 using namespace std;
 10 
 11 const int Maxn=200005,INF=0x3f3f3f3f;
 12 struct Edge{
 13     int to,v;
 14     Edge*next;
 15     Edge(int to=0,int v=0,Edge*next=NULL):to(to),v(v),next(next){
 16         
 17     }
 18 }pool[Maxn*2],*fir[Maxn],*pis;
 19 
 20 void AddEdge(int from,int to,int v){
 21     *pis=Edge(to,v,fir[from]);fir[from]=pis++;
 22     *pis=Edge(from,v,fir[to]);fir[to]=pis++;
 23 }
 24 
 25 int sz[Maxn],mx[Maxn];
 26 int vis[Maxn],clk;
 27 void dfs_size(int x,int fa) {
 28     sz[x]=1;
 29     mx[x]=0;
 30     for(Edge*p=fir[x];p;p=p->next) {
 31         if(p->to==fa || vis[p->to]==clk) continue;
 32         dfs_size(p->to,x);
 33         sz[x] += sz[p->to];
 34         mx[x] = max(mx[x],sz[p->to]);
 35     }
 36 }
 37 
 38 int root=0;
 39 void dfs_root(int r,int x,int fa) {
 40     mx[x] = max(mx[x],sz[r]-sz[x]);
 41     if(mx[root]>mx[x]) root=x;
 42     
 43     for(Edge*p=fir[x];p;p=p->next) {
 44         if(p->to==fa || vis[p->to]==clk) continue;
 45         dfs_root(r,p->to,x);
 46     }
 47 }
 48 
 49 int f[2000010];
 50 int g[2000010],seq[Maxn],top;
 51 void dfs_dis(int x,int d,int cnt,int fa) {
 52     if(d>1000000) return;
 53     seq[++top]=d;
 54     g[d]=min(g[d],cnt);
 55     for(Edge*p=fir[x];p;p=p->next) {
 56         if(p->to==fa || vis[p->to]==clk) continue;
 57         dfs_dis(p->to,d+p->v,cnt+1,x);
 58     }
 59 }
 60 
 61 int k;
 62 int ans;
 63 void dfs(int x) {
 64     dfs_size(x,0);
 65     root=0;
 66     dfs_root(x,x,0);
 67     vis[root]=clk;
 68     top=0;
 69     for(Edge*p=fir[root];p;p=p->next) {
 70         if(vis[p->to]==clk) continue;
 71         int l=top;
 72         dfs_dis(p->to,p->v,1,root);
 73         for(int i=l+1;i<=top;i++) if(k-seq[i]>=0) ans=min(ans,f[k-seq[i]]+g[seq[i]]);
 74         for(int i=l+1;i<=top;i++) f[seq[i]]=min(f[seq[i]],g[seq[i]]),g[seq[i]]=INF;
 75         g[0]=0;
 76     }
 77     for(int i=1;i<=top;i++) f[seq[i]]=INF;
 78     f[0]=0;
 79     for(Edge*p=fir[root];p;p=p->next) {
 80         if(vis[p->to]!=clk) dfs(p->to);
 81     }
 82 }
 83 int n;
 84 void init() {
 85     memset(mx,0,sizeof mx);
 86     mx[0]=INF;
 87     ans=INF;
 88     ++clk;
 89     memset(fir,0,sizeof fir);
 90     pis=pool;
 91     int u,v,w;
 92     for(int i=1;i<n;i++) {
 93         scanf("%d%d%d",&u,&v,&w);
 94         AddEdge(u+1,v+1,w);
 95     }
 96 }
 97 
 98 int main(){
 99 #ifdef DEBUG
100     freopen("in.txt","r",stdin);
101     freopen("out.txt","w",stdout);
102 #endif
103     
104     memset(f,0x3f,sizeof f);
105     memset(g,0x3f,sizeof g);
106     f[0]=g[0]=0;
107     for(;scanf("%d%d",&n,&k)==2;) {
108         init();
109         dfs(1);
110         printf("%d
",ans>=n?-1:ans);
111     }
112     
113     return 0;
114 }

View Code

注意每次的辅助数组f,g清空不能用memset清空所有数字，最好统计两个max_deep来清，这样复杂度才有保证，不然就是平方级的了。

还有vis数组只是用来标记重心的，以前一直理解错了。

树的重心 点分治

树的重心点分治