D. Happy Tree Party

Tree, RMQ(rmq), LCA(lca)


출처: Codeforces D. Happy Tree Party

SOL)
 두 점 a, b를 이어주는 간선을 모두 따라가면 Time limit
y의 최대값은 10^18으로 2이상의 수를 64번이상 나누면 0이
됨을 이용한다. a, b로 가는 도중에 지나가는 간선의 가중치가
1이면 두 점을 합쳐버린다. (Union Find)

 lca의 값은 선택된 두 점의 index값보다 같거나 작다는 특징을 이용



[-] Collapse

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 200005;

int par[N]; //union find
int T[8 * N]; //rmq lca table
int o_n[N]; //origin vertex to new indexing table
int up[N]; //edge to parent
int pos[N];
pair<pair<int, int>, ll> edge[N];
vector<int> adj[N];

int n, m;
int idx , c = 1, h = 1;

int find(int v){
    if (v == par[v]) return v;
    else return par[v] = find(par[v]);
}

void merge(int u, int v){
    u = find(u), v = find(v);
    if (u == v) return;
    if (u > v) swap(u, v);
    par[v] = u;
}
void dfs(int here, int prev){
    o_n[here] = c;
    pos[c++] = idx;
    T[idx++] = o_n[here];
    for (int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        if (o_n[next] == 0){
            dfs(next, here);
            T[idx++] = o_n[here];
        }
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < 8 * N; i++) T[i] = N;
    cin >> n >> m;
    for (int i = 1; i < n; i++){
        int u, v; ll d; cin >> u >> v >> d;
        adj[u].push_back(v); adj[v].push_back(u);
        edge[i] = make_pair(make_pair(u, v), d);
    }
    while (h < 2*(n-1)) h <<= 1;
    idx = h;
    dfs(1, 1);
    for (int i = h - 1; i >= 1; i--) T[i] = min(T[2 * i], T[2 * i + 1]);
    for (int i = 0; i <= n; i++) par[i] = i;
    for (int i = 1; i < n; i++){
        int u = o_n[edge[i].first.first];
        int v = o_n[edge[i].first.second];
        if (u > v) swap(u, v);
        edge[i].first.first = u;
        edge[i].first.second = v;
        up[v] = i;
        if (edge[i].second == 1) merge(u, v);
    }
    for (int i = 0; i < m; i++){
        int o; cin >> o;
        if (o & 1){
            int a, b; ll y; cin >> a >> b >> y;
            int l = pos[o_n[a]];
            int r = pos[o_n[b]];
            if (l > r) swap(l, r);
            int lca = N;
            while (l <= r){
                if (l & 1) lca = min(lca, T[l]);
                if (!(r & 1)) lca = min(lca, T[r]);
                l = (l + 1) >> 1;
                r = (r - 1) >> 1;
            }
            a = o_n[a]; b = o_n[b];
            while (y){
                a = find(a);
                if (a <= lca) break;
                y /= edge[up[a]].second;
                a = edge[up[a]].first.first;
            }
            while (y){
                b = find(b);
                if (b <= lca) break;
                y /= edge[up[b]].second;
                b = edge[up[b]].first.first;
            }
            cout << y << endl;
        }
        else{
            int idx; ll d;  cin >> idx >> d;
            edge[idx].second = d;
            if (d == 1) merge(edge[idx].first.first, edge[idx].first.second);
        }
    }
    return 0;
}