[ZJOI2015]幻想乡战略游戏

一句话题意：给棵树，有点权有边权

单点修改点权，维护带权重心

观察了各位dalao的博客依旧是没看透彻。。。

下课了，留个坑，明天早上补题解

代码里偷懒没写快读，还用的倍增LCA，开O2在洛谷上勉强卡过，不开O2T得飞起。。30分。。。

乱七八糟的代码

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int v, w, ne, rt;
} a[200010];

int h[100010], tmp;
int sz[100010], maxw[100010];
int father[100010];
bool vis[100010];
int fa[100010][18], depth[100010], dis[100010];
long long va[100010], num[100010], vb[100010];
int n, q, root, sum, root0;

void add(int x, int y, int z)
{
    a[++tmp] = (edge){y, z, h[x]};
    h[x] = tmp;
}

void getroot(int x, int fa)
{
    sz[x] = 1;
    maxw[x] = 0;
    for (int i = h[x]; i != 0; i = a[i].ne)
        if (fa != a[i].v && vis[a[i].v] == false)
        {
            getroot(a[i].v, x);
            sz[x] += sz[a[i].v];
            maxw[x] = max(maxw[x], sz[a[i].v]);
        }
    maxw[x] = max(maxw[x], sum - sz[x]);
    if (maxw[x] < maxw[root])
        root = x;
}

void getsz(int x, int fa)
{
    sz[x] = 1;
    for (int i = h[x]; i != 0; i = a[i].ne)
        if (fa != a[i].v && vis[a[i].v] == false)
            getsz(a[i].v, x), sz[x] += sz[a[i].v];
}

void solve(int x)
{
    vis[x] = true;
    getsz(x, 0);
    for (int i = h[x]; i != 0; i = a[i].ne)
        if (vis[a[i].v] == false)
            sum = sz[a[i].v], root = 0, getroot(a[i].v, 0), a[i].rt = root, father[root] = x, solve(root);
}

void dfs(int x)
{
    for (int i = h[x]; i != 0; i = a[i].ne)
        if (fa[x][0] != a[i].v)
            fa[a[i].v][0] = x, depth[a[i].v] = depth[x] + 1, dis[a[i].v] = dis[x] + a[i].w, dfs(a[i].v);
}

int lca(int x, int y)
{
    if (x == 0 || y == 0)
        return 0;
    if (depth[x] < depth[y])
        swap(x, y);
    int fuck = depth[x] - depth[y];
    for (int i = 17; i >= 0; i--)
        if (fuck & (1 << i))
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 17; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int getdis(int x, int y)
{
    return dis[x] + dis[y] - 2 * dis[lca(x, y)];
}

long long calc(int x)
{
    long long res = 0;
    for (int y = x; y != 0; y = father[y])
    {
        res += va[y] + num[y] * (long long)getdis(x, y);
        if (father[y] != 0)
            res -= vb[y] + num[y] * (long long)getdis(x, father[y]);
    }
    return res;
}

long long query()
{
    int x = root0;
    long long sb = calc(x), t;
    while (1)
    {
        int y = x;
        sb = calc(x);
        for (int i = h[x]; i != 0; i = a[i].ne)
            if (a[i].rt && (t = calc(a[i].v)) < sb)
                sb = t, y = a[i].rt;
        if (x == y)
            break;
        x = y;
    }
    return sb;
}

int main()
{
    scanf("%d%d", &n, &q);
    for (int x, y, z, i = 1; i < n; i++)
        scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z);
    maxw[0] = n, sum = n, getroot(1, 0), root0 = root, solve(root);
    dfs(1);
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int x, chenge, i = 1; i <= q; i++)
    {
        scanf("%d%d", &x, &chenge);
        for (int y = x; y != 0; y = father[y])
        {
            va[y] += chenge * (long long)getdis(x, y), num[y] += chenge;
            if (father[y] != 0)
                vb[y] += chenge * (long long)getdis(x, father[y]);
        }
        printf("%lld\n", query());
    }
    return 0;
}

[ZJOI2015]幻想乡战略游戏

原文：https://www.cnblogs.com/oier/p/10235898.html