[POI2008] STA-Station

很显然的递推式ans[q] = ans[p] + n - 2*siz[q];

这么个题你卡我常干嘛，害得我加快读

（谁叫我是vector党呢

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000006;

inline int read(){

    int s=0,w=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

    return s*w;

}

int n,siz[N],vis[N],sum[N],ans[N],t1,t2;

vector <int> g[N];

void dfs1(int p) {

    vis[p]=1;

    siz[p]=1;

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i];

        if(vis[q]==0) {

            dfs1(q);

            siz[p]+=siz[q];

            sum[p]+=sum[q]+siz[q];

        }

    }

}

void dfs2(int p) {

    vis[p]=1;

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i];

        if(vis[q]==0) {

            ans[q] = ans[p] + n - 2*siz[q];

            dfs2(q);

        }

    }

}

signed main() {

    n=read();

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

        t1=read();

        t2=read();

        g[t1].push_back(t2);

        g[t2].push_back(t1);

    }

    dfs1(1);

    ans[1]=sum[1];

    memset(vis,0,sizeof vis);

    dfs2(1);

    cout<<max_element(ans+1,ans+n+1)-ans;

}

巴特西

[POI2008] STA-Station - 树形dp

最新文章

热门文章