はじめに

AtCoder Beginner Contest 133 の解法です．

A - T or T

$N \times A$ と $B$ の小さい方が答えになります．

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(N * A, B) << endl;
    return 0;
}

B - Good Distance

2点間の距離の二乗 $d$ が整数 $x$ の二乗と等しくなるかチェックします．
整数 $x$ は $0$ から $\sqrt{d}$ まで試します．

int main() {
    int N, D, X[10][10];
    cin >> N >> D;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < D; j++) {
            cin >> X[i][j];
        }
    }
    int res = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int d = 0;
            for (int k = 0; k < D; k++) {
                d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }
            int sq = sqrt(d);
            for (int x = 0; x < sq + 1; x++) {
                if (x * x == d) {
                    res++;
                    break;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

C - Remainder Minimization

$R - L \geq 2019$ のとき，$2019$ の倍数が必ず存在するため，最小値は $0$ になります．
$R - L < 2019$ のとき，$L \leq i < j \leq R$ にしたがって，$i, j$ を動かして最小値を求めます．
計算量は高々 $2019^{2}$ になります．

int main() {
    long long L, R;
    cin >> L >> R;
    if (L % 2019 == 0 || R % 2019 == 0) {
        cout << 0 << endl;
        return 0;
    } else if (R - L >= 2019) {
        cout << 0 << endl;
        return 0;
    }
    int res = 2018;
    for (long long i = L; i < R; i++) {
        for (long long j = i + 1; j <= R; j++) {
            int r = i * j % 2019;
            res = min(res, r);
        }
    }
    cout << res << endl;
    return 0;
}

D - Rain Flows into Dams

各山に降った雨を $X_{i} (i = 1, \cdots, N)$ とすると，以下が成り立ちます．

\cfrac{X_{i}}{2} + \cfrac{X_{i + 1}}{2} = A_{i} \tag{1}

$i = 1$ から $i = N$ まで並べます．$X_{N + 1} = X_{1}$ としています．

X_{1} + X_{2} = 2 A_{1} \\
X_{2} + X_{3} = 2 A_{2} \\
X_{3} + X_{4} = 2 A_{3} \\
\cdots \\
X_{N} + X_{1} = 2 A_{N}

奇数行を足し，偶数行を引くと，以下を導くことができます．

X_{1} = A_{1} - A_{2} + A_{3} - \cdots + A_{N}

式(1)にしたがって $X_{i} (i = 2, \cdots, N)$ を順次求めます．

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), res(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (i % 2 == 0) {
            res[0] += A[i];
        } else {
            res[0] -= A[i];
        }
    }
    for (int i = 1; i < N; i++) {
        res[i] += A[i - 1] * 2 - res[i - 1];
    }
    for (int i = 0; i < N; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}

E - Virus Tree 2

頂点 $0$ を根として考えます．
頂点 $i$ の子の数を $c_{i}$ とすると，$i \neq 0$ なる頂点 $i$ の子を塗るとき $K - 2$ 色から $c_{i}$ 色選ぶことになります．
頂点 $0$ の子は $K - 1$ 色から選びます．

const int MOD = 1000000007;
int N, K;
vector<vector<int>> G;

long long dfs(int curr, int prev) {
    if (G[curr].size() > K) {
        return 0;
    }
    int k = prev == -1 ? K - 1 : K - 2;
    long long res = 1;
    for (auto x : G[curr]) {
        if (x == prev) {
            continue;
        }
        res *= k;
        res %= MOD;
        k--;
    }
    for (auto x : G[curr]) {
        if (x == prev) {
            continue;
        }
        res *= dfs(x, curr);
        res %= MOD;
    }
    return res;
}

int main() {
    cin >> N >> K;
    G = vector<vector<int>>(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cout << dfs(0, -1) * K % MOD << endl;
    return 0;
}

F - Colorful Tree

まずは2頂点間の距離を求めます．
根から頂点 $u$ までの距離を $d_{u}$ で表し，
$u, v$ の共通祖先のうち根から最も遠い頂点(lca)を $w$ とすると，
$u$ と $v$ の距離は $d_{u} + d_{v} - 2 d_{w}$ で計算できます．
頂点 $u$ の $2^{i}$ 個上の親を $p_{u, i}$ とすると $p_{u, i + 1} = p_{p_{u, i}, i}$ が成り立ちます．
$u, v$ の深さを揃えてから，親が一致しない境界まで上に辿るとlcaが求められます．
頂点ごとにクエリを登録しておき，dfsで探索するときに色の書き換えによる距離の変化量を計算します．

struct node {
    int to;
    int col;
    int dis;
};

struct query {
    int id;
    int col;
    int dis;
    int coef;
};

const int MAX_N = 100000;
const int MAX_LOGN = 20;
const int MAX_Q = 100000;
const int MAX_C = 100000 - 1;

vector<vector<node>> G(MAX_N);
vector<vector<query>> qs(MAX_N);

vector<vector<int>> par(MAX_N, vector<int>(MAX_LOGN, -1));
vector<int> dep(MAX_N, 0);
vector<int> dis(MAX_N, 0);
vector<int> cnt(MAX_C, 0);
vector<int> sum(MAX_C, 0);

vector<int> res(MAX_Q, 0);

void init(int u, int p = -1, int d = 0) {
    if (p >= 0) {
        par[u][0] = p;
        dep[u] = dep[p] + 1;
        dis[u] = dis[p] + d;
    }
    for (auto g : G[u]) {
        int v = g.to;
        if (v != p) {
            init(v, u, g.dis);
        }
    }
}
void parent(int n) {
    for (int i = 0; i < MAX_LOGN; i++) {
        for (int j = 0; i < n; i++) {
            if (par[j][i] != -1) {
                par[j][i + 1] = par[par[j][i]][i];
            }
        }
    }
}
int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    for (int i = MAX_LOGN - 1; i >= 0; i--) {
        if (((dep[v] - dep[u]) >> i) & 1) {
            v = par[v][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = MAX_LOGN - 1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
void dfs(int u, int p = -1) {
    for (auto q : qs[u]) {
        int diff = q.dis * cnt[q.col] - sum[q.col];
        res[q.id] += diff * q.coef;
    }
    for (auto g : G[u]) {
        int v = g.to;
        if (v == p) {
            continue;
        }
        cnt[g.col]++;
        sum[g.col] += g.dis;
        dfs(v, u);
        cnt[g.col]--;
        sum[g.col] -= g.dis;
    }
}

int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        G[a].push_back({b, c, d});
        G[b].push_back({a, c, d});
    }
    init(0);
    parent(N);
    for (int i = 0; i < Q; i++) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        u--, v--;
        int w = lca(u, v);
        qs[u].push_back({i, x, y, 1});
        qs[v].push_back({i, x, y, 1});
        qs[w].push_back({i, x, y, -2});
        res[i] = dis[u] + dis[v] - 2 * dis[w];
    }
    dfs(0);
    for (int i = 0; i < Q; i++) {
        cout << res[i] << endl;
    }
    return 0;
}