http://www.lydsy.com/JudgeOnline/problem.php?id=1131
两遍DFS
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
const int MAXN=1000010;
int n;
struct edge{int v,next;}e[MAXN*2];
int head[MAXN],k;
LL cnt[MAXN],dep[MAXN],sum[MAXN];
LL ans,mmax;
/////////////////////////////////////////////////
void adde(int u,int v){e[k].v=v;e[k].next=head[u];head[u]=k++;}
void dfs1(int u,int fa)
{
cnt[u]=1;
INE(i,u,e)
{
int v=e[i].v;
if(v==fa) continue;
dep[v]=dep[u]+1;
dfs1(v,u);
cnt[u]+=cnt[v];
sum[u]+=cnt[v]+sum[v];
}
}
void dfs2(int u)
{
INE(i,u,e)
{
int v=e[i].v;
if(dep[v]<dep[u]) continue;
sum[v]=sum[u]-cnt[v]+(n-cnt[v]);
dfs2(v);
}
}
/////////////////////////////////////////////////
void input()
{
MS(head,-1);
scanf("%d",&n);
int u,v;
rep(i,1,n-1)
{
scanf("%d%d",&u,&v);
adde(u,v); adde(v,u);
}
}
void solve()
{
///////////////////init///////////////////
mmax=0;
////////////////calculate////////////////
dep[1]=1;
dfs1(1,-1);
dfs2(1);
//rep(i,1,n) printf("%d ",sum[i]);
rep(i,1,n) if(mmax<sum[i]) mmax=sum[i],ans=i;
/////////////////output/////////////////
printf("%lld",ans);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("1131.in","r",stdin); freopen("1131.out","w",stdout);
#endif
input();
solve();
#ifdef _TEST
for(;;);
#endif
return 0;
}
http://www.lydsy.com/JudgeOnline/problem.php?id=2435
切这种水题还是很轻松的
不过是NOI，一种莫名的自豪感，就放上来吧
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
const int N=1000010;
int n;
struct edge{int v,w,next;}e[N*2];
int head[N],k;
LL ans;
int sz[N];
/////////////////////////////////////////////////
inline int abs(int a){return a>0?a:-a;}
void adde(int u,int v,int w){e[k].v=v;e[k].w=w;e[k].next=head[u];head[u]=k++;}
inline int getint()
{
int res=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res;
}
void dfs(int u,int fa)
{
sz[u]=1;
INE(i,u,e)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
ans+=(LL)e[i].w * abs(n-2*sz[v]);
}
}
/////////////////////////////////////////////////
void input()
{
MS(head,-1);
n=getint();
int u,v,w;
rep(i,1,n-1) u=getint(),v=getint(),w=getint(),
adde(u,v,w),adde(v,u,w);
}
void solve()
{
///////////////////init///////////////////
////////////////calculate////////////////
dfs(1,-1);
/////////////////output/////////////////
printf("%lld\n",ans);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
input();
solve();
#ifdef _TEST
for(;;);
#endif
return 0;
}
经典问题
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n;
struct edge{
int v,w,next;
}e[10010];
int head[10010],k;
int dp[10010][3];
/////////////////////////////////////////////////
void adde(int u,int v,int w){e[k].v=v;e[k].w=w;e[k].next=head[u];head[u]=k++;}
void dfs1(int u)
{
dp[u][0]=dp[u][1]=0;
INE(i,u,e)
{
int v=e[i].v;
dfs1(v);
int tmp=dp[v][0]+e[i].w;//为什么不用dp[v][1]更新，自己脑补
if(dp[u][0]<tmp)
{
dp[u][1]=dp[u][0];
dp[u][0]=tmp;
}
else if(dp[u][1]<tmp)
{
dp[u][1]=tmp;
}
}
}
void dfs2(int u)
{
INE(i,u,e)
{
int v=e[i].v;
dp[v][2]=max(dp[u][2],dp[u][0]==dp[v][0]+e[i].w?dp[u][1]:dp[u][0])+e[i].w;
dfs2(v);
}
}
/////////////////////////////////////////////////
void input()
{
MS(head,-1); k=0;
int u,w;
rep(v,2,n)
{
u=read(); w=read();
adde(u,v,w);
}
}
void solve()
{
dfs1(1);
dfs2(1);
rep(i,1,n) printf("%d\n",max(dp[i][0],dp[i][2]));
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
while(~scanf("%d",&n))
input(),solve();
return 0;
}