大意: 给定n结点树, 求构造一种染色方案, 使得每个点颜色在[A,Z], 且端点同色的链中至少存在一点颜色大于端点 (A为最大颜色)

 

直接点分治即可, 因为最坏可以涂$2^{26}-1$个节点, 所以方案一定存在

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define REP(i,a,n) for(int i=a;i<=n;++i)#define pb push_backusing namespace std;typedef long long ll;const int N = 4e5+10, INF = 0x3f3f3f3f;int n, sum, rt;int mx[N], sz[N], vis[N];vector
         
           g[N];char buf[N];void getrt(int x, int fa) {	mx[x]=0, sz[x]=1;	for (int y:g[x]) if (!vis[y]&&y!=fa) {		getrt(y,x),sz[x]+=sz[y];		mx[x]=max(mx[x],sz[y]);	}	mx[x]=max(mx[x],sum-sz[x]);	if (mx[x]