codeforces 321 C Ciel the Commander 点分治

cf 321 C

题意 给你一棵树 它的边 叫你赋上点值 A最大 然后要你两个相同的点值中间要有个高的 比如B和B中间要有个A

样例1 就是这个意思

我们怎么考虑呢 你既然要有个高的 那么我只要每次重心设置能没出现过的最高的值 这样就可以分成两块 所以接下来的两块可以继续这样弄 最多2^26 >1e5 所以肯定是有答案的 不会有impossible 

具体看代码吧

/*
codeforces 321 C
*/
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_N = 100024;
int f[MAX_N],siz[MAX_N];
struct edge{
    int next,v,dis;
}e[MAX_N<<1];
char s[MAX_N];
int eid,p[MAX_N],use[MAX_N],Siz,rt,n,cnt,d[MAX_N],ans;
inline int read(){
    int date = 0, m = 1;
    char ch = 0;
    while(ch!='-'&&(ch<'0'||ch>'9'))
        ch = getchar();
    if(ch=='-'){
        m = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        date = date*10+ch-'0';
        ch = getchar();
    }
    return date*m;
}
void init(){
    memset(p,-1,sizeof(p));
    memset(use,0,sizeof(use));
    memset(d,0,sizeof(d));
    rt = 0;
    f[rt] = Siz = n;
    eid = 0;
}
void Insert(int u,int v){
    e[eid].v = v;
    e[eid].next = p[u];
    p[u] = eid++;
}
void get_rt(int u,int fa){
    f[u] = 0,siz[u] = 1;
    for(int i = p[u];i!=-1;i=e[i].next){
        int y = e[i].v;
        if(use[y]||y==fa) continue;
        get_rt(y,u);
        f[u] = max(f[u],siz[y]);
        siz[u] += siz[y];
    }
    f[u] = max(f[u],Siz - siz[u]);
    if(f[u]<f[rt]) rt = u;
}
void dfs(int u,int dep){
    use[u] = 1;
    s[u] = dep+ 'A';
    for(int i = p[u];~i;i=e[i].next){
        int y = e[i].v;
        if(use[y]) continue;
        Siz = siz[y],rt = 0;
        get_rt(y,u),dfs(rt,dep+1);
    }

}
int main(){
    n = read();
    init();
    for(int i = 1;i<n;++i){
        int a,b;
        a = read(),b=read();
        Insert(a,b);
        Insert(b,a);
    }
    get_rt(1,0);
    dfs(rt,0);
    for(int i = 1;i<=n;++i){
        i==n?printf("%c\n",s[i]):printf("%c ",s[i]);
    }
    return 0;
}