点分治基本膜版

点分治基本的几个步骤吧

找根（保证平衡度最优）

从找到的根处理起，每次删去已有的根，分治其每一个子树

非暴力算法解决树形问题的有效方式

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch;
10     int re=0;
11     bool flag=0;
12     while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
13     ch=='-'?flag=1:re=ch-'0';
14     while((ch=getchar())>='0'&&ch<='9')  re=re*10+ch-'0';
15     return flag?-re:re;
16 }
17 
18 struct edge{
19     int to,w;
20     edge(int to=0,int w=0):
21         to(to),w(w){}
22 };
23 
24 const int maxn=10001,maxm=50001;
25 int n;
26 vector<edge> G[maxn];
27 int son[maxn],F[maxn],sum;
28 bool vis[maxn];
29 int root;
30 
31 inline void add_edge(int from,int to,int w){
32     G[from].push_back(edge(to,w));
33     G[to].push_back(edge(from,w));
34 }
35 
36 void init(){
37     n=read();
38     for(int i=0;i<n-1;i++){
39         int from=read(),to=read(),w=read();
40         add_edge(from,to,w);
41     }
42 }
43 
44 void getroot(int x,int fa){
45     son[x]=1;
46     F[x]=0;
47     int dd=G[x].size();
48     for(int i=0;i<dd;i++){
49         edge &e=G[x][i];
50         if(e.to!=fa&&!vis[e.to]){
51             getroot(e.to,x);
52             son[x]+=son[e.to];
53             F[x]=max(F[x],son[e.to]);
54         }
55     }
56     F[x]=max(F[x],sum-son[x]);
57     if(F[x]<F[root])  root=x;
58 }
59 
60 void solve(int x){
61     vis[x]=1;
62     int dd=G[x].size();
63     for(int i=0;i<dd;i++){
64         edge &e=G[x][i];
65         if(!vis[e.to]){
66             root=0;
67             sum=e.to;
68             getroot(x,0);
69             solve(e.to);
70         }
71     }
72 }
73 
74 int main(){
75     //freopen("temp.in","r",stdin);
76     init();
77     sum=F[root=0]=n;
78     memset(vis,0,sizeof vis);
79     getroot(1,0);
80     printf("%d
",root);
81     memset(vis,0,sizeof vis);
82     solve(root);
83     return 0;
84 }

理想永远都年轻你让我倔强地反抗着命运