求条P6037

#include <bits/stdc++.h>
using namespace std;
struct b
{
    int v;
    int w;
    int p;
};
int n, e, ew, ep, ans[1000005], sum;
bool vis[1000005];
vector<b> q[1000005];
vector<int> h;
bool dfs(int u, int fa, int w, int p)
{
    if (vis[u])
    {
        e = u;
        ew = w;
        ep = p;
        return 1;
    }
    vis[u] = 1;
    for (int i = 0; i < q[u].size(); i++)
    {
        if (q[u][i].v == fa)
        {
            continue;
        }
        if (dfs(q[u][i].v, u, q[u][i].w, q[u][i].p))
        {
            if (u != e)
            {
                if (ep > q[u][i].p)
                {
                    ans[u] -= q[u][i].w;
                }
                else
                {
                    ans[u] -= ew;
                }
                h.push_back(u);
                return 1;
            }
            else
            {
                if (ep > q[u][i].p)
                {
                    ans[u] -= q[u][i].w;
                }
                else
                {
                    ans[u] -= ew;
                }
                h.push_back(u);
                return 0;
            }
        }
    }
    return 0;
}
void dfs1(int u)
{
    vis[u] = 1;
    for (int i = 0; i < q[u].size(); i++)
    {
        if (vis[q[u][i].v])
        {
            continue;
        }
        ans[q[u][i].v] = ans[u];
        dfs1(q[u][i].v);
    }
    return;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u, v, w, p;
        cin >> u >> v >> w >> p;
        q[u].push_back(b{v, w, p});
        q[v].push_back(b{u, w, p});
        sum += w;
    }
    dfs(1, 0, 0, 0);
    fill(vis + 1, vis + n + 1, 0);
    for (int i = 0; i < h.size(); i++)
    {
        vis[h[i]] = 1;
        ans[h[i]] += sum;
    }
    for (int i = 0; i < h.size(); i++)
    {
        dfs1(h[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}