bzoj1131 Sta

Description

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.

Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个.

Sample Input

8

1 4

5 6

4 5

6 7

6 8

2 4

3 4

Sample Output

7

简单的树形dp

现在智障错误越来越多,忘开long long气死人

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e6+10;
int n;

int aa;char cc;
int read() {
    aa=0;cc=getchar();
    while(cc<‘0‘||cc>‘9‘) cc=getchar();
    while(cc>=‘0‘&&cc<=‘9‘) aa=aa*10+cc-‘0‘,cc=getchar();
    return aa;
}

int fir[maxn],nxt[2*maxn],to[2*maxn],e=0;
void add(int x,int y) {
    to[++e]=y;nxt[e]=fir[x];fir[x]=e;
    to[++e]=x;nxt[e]=fir[y];fir[y]=e;
}

long long fa[maxn],size[maxn],ans[maxn];//
void dfs1(int pos,long long d) {
    int z;size[pos]=1;ans[1]+=d;
    for(int y=fir[pos];y;y=nxt[y]) {
        z=to[y];
        if(z==fa[pos]) continue;
        fa[z]=pos; dfs1(z,d+1);
        size[pos]+=size[z];
    }
}

void dfs2(int pos) {
    if(pos!=1) ans[pos]=ans[fa[pos]]+n-2*size[pos];
    int z;
    for(int y=fir[pos];y;y=nxt[y]) {
        z=to[y];
        if(z==fa[pos]) continue;
        dfs2(z);
    }
}

int main() {
    n=read();int x,y;
    for(int i=1;i<n;++i) {
        x=read();y=read();
        add(x,y);
    }
    dfs1(1,1);
    dfs2(1); int pos=1;
    for(int i=2;i<=n;++i) if(ans[i]>ans[pos]) pos=i;
    printf("%d",pos);
    return 0;
}

  

时间: 09-06

bzoj1131 Sta的相关文章

bzoj-1131 Sta

题意: 给出一个n个点的树,找出一个点来,使以这个点为根的树所有点的深度之和最大: n<=1000000: 题解: 其实我做这道题的时候总有一种莫名其妙的即视感怎么回事... 算了说不定这道题我真的做过... 比较暴力的是将所有点枚举,然后深搜累加所有深度: 但是显然所有点等于父树的点+子树的点: 那么只要求出这两者累加就好了: 子树的总深度简直好求,就是将儿子的总深度+size就好了: 父树的稍微有点麻烦,因为需要一些预处理所以在第二次深搜解决: 对于一个点来说,这个点的父树就是[父亲+父亲的

[BZOJ1131][POI2008] Sta 树的深度

Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input 给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. Output 输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input81 45 64 56 76 82 43 4 Sample Output7 题解: 都说是裸树形DP,其实我做的时候就是把它当成搜索去做了,当然是一个意思.假设当前的根为1,先求出每棵子树的大小,以及所有点的深度之和.考虑

BZOJ1131 [POI2008]Sta 其他

原文链接http://www.cnblogs.com/zhouzhendong/p/8081100.html 题目传送门 - BZOJ1131 题意概括 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大. 题解 嘻,这题不卡栈. 假设以1为根 先跑一遍dfs,算出每一个子树的节点数size,同时算出以1为根节点的深度和. 然后再跑一遍dfs,这一回,我们就可以算答案了. 假设我们要把树根从一条边的一个节点移向另一个节点,那么,这两个节点为根的答案差就是这条边两端的节点个

[BZOJ1131][POI2008]Sta

题目描述 Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 输入描述 Input Description 给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. 输出描述 Output Description 输出你所找到的点,如果具有多个解,请输出编号最小的那个. 样例输入 Sample Input 81 45 64 56 76 82 43 4 样例输出 Sample Output 7 数据范围及提示 Data Size &

1131: [POI2008]Sta

1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 783  Solved: 235[Submit][Status] Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input 给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. Output 输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input 8 1 4 5 6

【转载】STA 4273H Winter 2015 - Lectures

STA4273H Home   Lecture Schedule/Notes Assignments/Project Computing   Ruslan Salakhutdinov Homepage http://www.cs.toronto.edu/~rsalakhu/   STA 4273H Winter 2015 - Lectures Video Archive here. Lecture Schedule Lecture 1 -- Machine Learning:Introducti

FolderBrowserDialog 关于设置为单线程单元(STA)模式的问题

当Main函数是这样的状态的时候,当打开FolderBrowserDialog控件的时候 ,报错 这里有两种解决办法,第一种,就是把main 上加[STAThread] 第二种是启用一个线程 Thread newThread = new Thread(new ThreadStart(ToOpenBD));//初始化线程 参数是委托  ToOpenBD是方法名字,没有参数            newThread.SetApartmentState(ApartmentState.STA);//设置

BZOJ 1131: [POI2008]Sta

1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1370  Solved: 486[Submit][Status][Discuss] Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input 给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. Output 输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input

Timequest静态时序分析(STA)基础

Setup Slack Hold Slack Recovery&Removal Recovery: The minimum time an asynchronous signal must be stable BEFORE clock edgeRemoval  : The minimum time an asynchronous signal must be stable AFTER clock edge I/O Analysis Analyzing I/O performance in a s