GYM100376F.Circle and Trees（树形DP+倍增LCA）

题意：

给你一棵树，请你为每个点确定一个圆（圆心坐标和半径）

这里要求：

圆心坐标和半径必须是整数，同时每个圆没有交点，同时每个点的圆必须包含它的子树的圆。

题解：

树形DP，DP的时候处理出每个叶子到根的路径上第一个有前驱兄弟的节点，这个叶子的圆心坐标确定了，它的祖先的坐标也就确定了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int n;
vector<int> g[maxn];
int tot=0;
int L[maxn],R[maxn];
int dfn[maxn];
int father[20][maxn];
int h[maxn];
int pre[maxn];//该节点到根的路径上第一个有前驱兄弟的点的前驱 
void dfs1 (int x,int xx) {
    int tt=0;
    pre[x]=xx;
    //printf("%d %d
",x,xx);
    for (int i=0;i<g[x].size();i++) {
        int y=g[x][i];
        if (y==father[0][x]) continue;
        father[0][y]=x;
        h[y]=h[x]+1;
        if (tt) {
            dfs1(y,tt);
        }
        else {
            dfs1(y,xx);
        }
        tt=y;
    }
}
int lca (int x,int y) {
    if (h[x]<h[y]) swap(x,y);
    for (int i=17;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x];
    if (x==y) return x;
    for (int i=17;i>=0;i--) {
        if (father[i][x]!=father[i][y]) {
            x=father[i][x];
            y=father[i][y];
        }
    }
    return father[0][x];
}
void dfs (int x) {
    tot++;
    dfn[tot]=x;
    int Min=1e6,Max=-1e6;
    if (g[x].size()==0) {
        if (pre[x]==0) {
            L[x]=-1e6+h[x];
            R[x]=L[x]+2;
            return;
        } 
        int lc=lca(x,pre[x]);
        L[x]=R[pre[x]]+1+h[x]-h[lc];
        R[x]=L[x]+2;
        return;
    }
    for (int y:g[x]) {
        dfs(y);
        Min=min(Min,L[y]);
        Max=max(Max,R[y]);
    }
    L[x]=Min-1;
    R[x]=Max+1;
    //printf("%d: %d %d
",x,L[x],R[x]);
}
int main () {
    scanf("%d",&n);
    int rt;
    for (int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        if (x==-1)
            rt=i;
        else
            g[x].push_back(i);
    }
    dfs1(rt,0);
    for (int i=1;i<=17;i++) for (int j=1;j<=n;j++) father[i][j]=father[i-1][father[i-1][j]];
    //for (int i=1;i<=n;i++) printf("%d ",pre[i]);
    //printf("
");
    dfs(rt);
    for (int i=1;i<=n;i++) printf("%d %d %d
",(L[i]+R[i])/2,0,(R[i]-L[i]+1)/2);
//    int f=1;
//    for (int i=1;i<=n;i++) if ((L[i]+R[i])%2) f=0;
//    for (int i=1;i<=n;i++) {
//        for (int j=1;j<=n;j++) {
//            if (L[i]>R[j]||R[i]<L[j]) continue;
//            f=0;
//        }
//    }
//    printf("%d
",f);
}