[POI2008]Station

题目大意：
　　给定一棵n个结点的树，求一个点x作为根，使得所有结点到x的距离和最小。

思路：
　　树形DP。
　　首先考虑将1作为根的情况。
　　很显然我们可以用一遍O(n)的DFS预处理出每个结点所对应子树大小size和子树内每个结点到这个结点的距离和sum。
　　这样也就相当于我们递推求出了以1作为根时各结点到它的距离和。
　　现在考虑将根往下转移。
　　假设我们现在要从u转移到v，那么显然在sum[u]的基础上，sum[v]需要变化的是(u,v)之间的连接的边。
　　也就是说sum[y]=sum[x]+n-size[y]*2。
　　这样我们就可以用O(n)时间将根往下转移。
　　总的时间复杂度还是O(n)的。

 #include<cstdio>

 #include<cctype>

 typedef long long int64;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 int head[N],to[N<<],next[N<<],sz;

 inline void add_edge(const int &u,const int &v) {

     to[++sz]=v; next[sz]=head[u]; head[u]=sz;

     to[++sz]=u; next[sz]=head[v]; head[v]=sz;

 }

 int64 sum[N],max;

 int n,size[N],root;

 void dfs(const int &x,const int &par) {

     size[x]=;

     for(int i=head[x];i;i=next[i]) {

         const int &y=to[i];

         if(y==par) continue;

         dfs(y,x);

         size[x]+=size[y];

         sum[x]+=sum[y]+size[y];

     }

 }

 void move(const int &x,const int &par) {

     if(sum[x]>max) {

         max=sum[x];

         root=x;

     } else if(sum[x]==max&&x<root) {

         root=x;

     }

     for(int i=head[x];i;i=next[i]) {

         const int &y=to[i];

         if(y==par) continue;

         sum[y]=sum[x]+n-size[y]*;

         move(y,x);

     }

 }

 int main() {

     n=getint();

     for(register int i=;i<n;i++) {

         add_edge(getint(),getint());

     }

     dfs(,);

     move(,);

     printf("%d\n",root);

     return ;

 }

巴特西

[POI2008]Station

最新文章

热门文章