bzoj2435:[Noi2011]道路修建(dfs手工栈)

Author Avatar
Sakits 3月 07, 2018

题解

  为什么NOI会有这种一眼题…随手写完才知道要写手工栈= =…
  所以这篇博客就记录一下dfs手工栈怎么写吧QAQ 说不定以后用得上

流程

  大概分为三个部分。
  第一部分:取出栈顶的点xx,注意不能弹出,只是取出来。如果xx出边到达的点是父亲的话就把这条边从邻接表里删除
  第二部分:如果xx的邻接表没有边了,说明已经遍历完所有儿子了,出栈,并计算其对父亲的贡献,然后continue
  第三部分:如果xx的邻接表中还有边才会到达第三部分。将下一条出边到达点yy加入栈中,将其yy的父亲记录为xx,初始化一下yy需要的各种信息,然后把这条出边从xx的邻接表里删除

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=1000010;
struct poi{int too, dis, pre;}e[maxn<<1];
int n, x, y, z, tot, top;
int last[maxn], size[maxn], st[maxn], fa[maxn], falen[maxn];
ll ans;
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline void add(int x, int y, int z){e[++tot]=(poi){y, z, last[x]}; last[x]=tot;}
void dfs(int x)
{
	st[++top]=x;
	while(top)
	{
		x=st[top]; 
		if(last[x] && e[last[x]].too==fa[x]) last[x]=e[last[x]].pre;
		if(!last[x])
		{
			top--; size[fa[x]]+=size[x];
			ans+=1ll*falen[x]*abs(size[x]-(n-size[x]));
			continue;
		}
		int i=last[x], too; 
		falen[too=e[i].too]=e[i].dis;
		fa[too]=x; st[++top]=too; last[x]=e[i].pre;
	}
}
int main()
{
	read(n);
	for(int i=1;i<n;i++) read(x), read(y), read(z), add(x, y, z), add(y, x, z);
	for(int i=1;i<=n;i++) size[i]=1;
	dfs(1); printf("%lld\n", ans);
}