Article From:https://www.cnblogs.com/zgglj-com/p/9060499.html

Title: http://codeforces.com/gym/101161

The solution: the K large of a chain in the tree, at the time of DFS Update, each line tree maintains the tree’s root to a chain of the node, and then the multiple line trees are organized into the chairman tree. For u (V), we directly deal with u, V, Lca (U, V) three chains.The simple path of this node is called the chain, because the line tree maintains the chain, so the chairman tree is directly queried and it is the same as that of the interval K. I always talk about line segments, because I think the chairman tree is the way to organize multiple line segments, and the emphasis is still on line segment trees. Each line of this problemThe section tree maintains a chain!!!

Feel: block code (such as LCA) must ensure correctness, otherwise it’s hard to tune up, orzzzzzzzz

#pragma warning(disable:4996)
#include<queue>
#include<map>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mem(arr,in) memset(arr,in,sizeof(arr))
using namespace std;

const int maxn = 50005;

int kase, n, q, tot, cnt, Max;
int root[maxn], pa[maxn][20], dp[maxn], head[maxn];

struct node { int to, va, next; } e[maxn * 2];
struct code { int l, r, sum; } T[maxn * 20];

void Inite() {
    Max = tot = cnt = 0;
    mem(dp, 0);
    mem(pa, -1);
    mem(head, -1);
}

void addedge(int u, int v, int w) {
    e[tot].to = v;
    e[tot].va = w;
    e[tot].next = head[u];
    head[u] = tot++;
}

void Update(int l, int r, int &rt, int pre, int p) {
    T[++cnt] = T[pre], T[cnt].sum++, rt = cnt;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mid >= p) Update(l, mid, T[rt].l, T[pre].l, p);
    else Update(mid + 1, r, T[rt].r, T[pre].r, p);
}

int Query(int l, int r, int x, int y, int z, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int sum = T[T[x].l].sum + T[T[y].l].sum - 2 * T[T[z].l].sum;
    if (sum >= k) return Query(l, mid, T[x].l, T[y].l, T[z].l, k);
    else return Query(mid + 1, r, T[x].r, T[y].r, T[z].r, k - sum);
}

void DFS(int u, int p,int deep) {
    pa[u][0] = p;
    dp[u] = deep;
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (v != p) {
            Update(1, Max, root[v], root[u], e[i].va);
            DFS(v, u, deep + 1);
        }
    }
}

void Getpa() {
    DFS(1, -1, 0);
    for (int i = 1; (1 << i) <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pa[j][i - 1] > 0) pa[j][i] = pa[pa[j][i - 1]][i - 1];
        }
    }
}

int Lca(int u, int v) {
    if (dp[u] > dp[v]) swap(u, v);
    for (int i = 0; i <= 19; i++) if ((dp[v] - dp[u]) >> i & 1) v = pa[v][i];        //Don't jump over the headif (u == v) return u;
    for (int i = 19; i >= 0; i--) if (pa[u][i] != pa[v][i]) {
        u = pa[u][i];
        v = pa[v][i];
    }
    return pa[u][0];
}

int main()
{
    scanf("%d", &kase);
    while (kase--) {
        scanf("%d", &n);
        Inite();
        for (int i = 2; i <= n; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
            Max = max(Max, w);
        }

        Getpa();

        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            int u, v;
            scanf("%d%d", &u, &v);

            int x = Lca(u, v);
            int p = dp[u] + dp[v] - 2 * dp[x];          //Judge the path with a few sidesif (p % 2) {
                double ans = (double)Query(1, Max, root[u], root[v], root[x], p / 2 + 1);
                printf("%.1lf\n", ans);
            }
            else {
                double ans = (double)Query(1, Max, root[u], root[v], root[x], p / 2) + (double)Query(1, Max, root[u], root[v], root[x], p / 2 + 1);
                printf("%.1lf\n", ans / 2);
            }
        }
    }
    return 0;
}

 

Link of this Article: ACM Tax

Leave a Reply

Your email address will not be published. Required fields are marked *