srO %%% $Jan$ %%% Orz
jian是我萌的绿太阳!
来跟我一起念: 栈(jian四声)

懵逼的 题目

传送至 Codevs

扯淡的 题解

woc这不是个sb题(flag $\times1$)?
RE
woc数组开大点就A了吧(flag $\times2$)?
MLE
woc栈溢出了?? xjb优化一下就A了吧(flag $\times3$)?
RE
woc还得写手工栈?? 2h后…这肯定能A吧(flag $\times4$)?
没过样例

人生成就达成(1 / 1): flag四连


手工栈啊…实在是太恶心了…自己看着理解吧…
注释挺详细的…

沙茶的 代码

// codevs1947.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (1000000 + 5)
#define INF (1000000 + 5)
#define LL long long 
const int root = 1;
using namespace std;

struct edg
{
    int from;
    int to;
    LL cost;
    int next;
};
int n;
LL ans;
edg b[MAXN << 1];
int cntb = 0;
int g[MAXN];
int cur[MAXN];// 当前的节点找到那个子节点了
int f[MAXN];
int fa[MAXN];

inline void adn(int, int, LL);
void dfs(int);
inline LL mabs(LL);
int main()
{
    cin >> n;
    int srx, sry, srz;
    for (int i = 1; i < n; i++)
    {
        cin >> srx >> sry >> srz;
        adn(srx, sry, srz);
        adn(sry, srx, srz);
    }
    fa[root] = 0;
    dfs(root);
    cout << ans;
    return 0;
}
inline void adn(int from, int to, LL cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    cur[from] = g[from] = cntb;
}
inline LL mabs(LL x)
{
    return (x > 0) ? (x) : (-x);
}
void dfs(int startDash)
{
    bool v[MAXN];// 可有可无?
    memset(v, false, sizeof(v));
    stack<int> jian;// %%%jian
    for (int i = 1; i <= n; i++)    f[i] = 1;// 初始化应该放在这里否则gg(或者说我不放在这里就不会写了TUT)
    jian.push(startDash);
    while (!jian.empty())
    {
        int dq = jian.top();// 这个地方不能弹栈, 因为还需要回溯
        v[dq] = true;
        if (!cur[dq])// 注意判定条件: 当前点没有可走的后继了
        {
            f[fa[dq]] += f[dq];// 更新父节点的 f 值
            for (int i = g[dq]; i; i = b[i].next)// 更新 ans
            {
                if (fa[dq] != b[i].to)
                    ans += (LL)mabs((n - f[b[i].to]) - f[b[i].to]) * b[i].cost;
            }
            jian.pop();// 没有后继, 需要回溯的时候再弹栈
            continue;
        }
        for (int i = cur[dq]; i; i = b[i].next)// 从上一次找完的子节点开始找起
        {
            bool ok = false;// 找到子节点的标志
            if (fa[dq] != b[i].to && !v[b[i].to])
            {
                fa[b[i].to] = dq;
                jian.push(b[i].to);
                ok = true;
            }
            cur[dq] = b[i].next;// 不管能不能走, 都要把这条边设为已经找过
            if (ok)
            {
                break;
            }
        }
    }
}
/*
void dfs(int dq)
{
    f[dq] = 1;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (fa[dq] != b[i].to)
        {
            fa[b[i].to] = dq;
            dfs(b[i].to);
            f[dq] += f[b[i].to];
        }
    }
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (fa[dq] != b[i].to)
            ans += (LL)mabs((n - f[b[i].to]) - f[b[i].to]) * b[i].cost;
    }
}
*/
/*
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
*/

By 被$Jan$碾压着的 Cansult

jan!