CF竞赛题目讲解_CF741D(树上启发式合并)

// https://codeforces.com/contest/741/problem/D

//  与下题类似

// https://ac.nowcoder.com/acm/contest/4853/E  旗鼓相当的对手

#include "stdafx.h"

//#include <bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<iostream>

#include <algorithm> 

#include <vector> 

using namespace std;

typedef long long ll;

const int N = 5e5+4;

 

int n,cur;

vector<pair<int,int>> adj[N];

int son[N];

int L[N],R[N],V[N],sz[N],h[N],dis[N];

int d[1<<22],ans[N];

void dfs1(int u){ 

sz[u] = 1;// 子树大小

V[L[u] = cur++] = u;

for (auto i : adj[u]){

h[i.first] = h[u] + 1;// 顶点深度, 根的深度为0

dis[i.first] = dis[u]^(1<<i.second);// 路径上的字母统计(只保留2的余数)

dfs1(i.first); 

sz[u] += sz[i.first];

if(sz[i.first] > sz[son[u]]) son[u]=i.first;

}

R[u] = cur;//  子树dfs编号结束位置

cout<<dis[u]<<", u="<<u<<endl;

}

void path(int v,int u){ 

cout<<dis[u]<<", u="<<u<<", h[v]="<<h[v]<<",h[u]="<<h[u]<<endl;

//  假设另外一个顶点x， dis[x]^dis[v]  必须是0 或者 1<<i(字母相同， 或者相差一个字母),

//  则x与v的路径上字母可以组成回文。

//  顶点x的深度是d[dis[v]]或者d[dis[v]^(1<<i)]， 所以x与v的路径长度(x与v在u的不同分支)：

//  d[dis[v]] + h[v] - 2*h[u] 或者 d[dis[v]^(1<<i)] + h[v] - 2*h[u]

//  如果u是1的话，h[u]=0， x与v的路径长度即为两者深度之和

if(d[dis[v]])ans[u] = max(ans[u], d[dis[v]] + h[v] - 2*h[u]);

cout<<ans[u]<<", d[dis[v]]="<<d[dis[v]]<<",v="<<v<<endl;

for (int i=0; i<22; i++)

{

if(d[dis[v]^(1<<i)])ans[u] = max(ans[u], d[dis[v]^(1<<i)] + h[v] - 2*h[u]);

//if(u==1 && v==5)cout<<ans[u]<<", [dis[v]]="<<(dis[v]^(1<<i))<<endl;

}

cout<<"ans[u]="<<ans[u]<<", d[dis[v]]="<<d[dis[v]]<<endl;

}

void dfs2(int u,bool f){

ans[u] = 0; 

for (auto i : adj[u]) 

if (i.first != son[u]){

dfs2(i.first, 0); ans[u] = max(ans[u], ans[i.first]);

}

if (son[u]){

dfs2(son[u], 1); 

ans[u] = max(ans[u], ans[son[u]]);

path(u, u);

}

d[dis[u]] = max(d[dis[u]], h[u]);// 字母集合达到的最大深度

cout<<"深度：u="<<u<<", dis[u]="<<dis[u]<<", d[dis[u]]="<<d[dis[u]]<<endl;

for (auto i: adj[u]) 

if (i.first != son[u]){

for (int k=L[i.first]; k<R[i.first]; k++) path(V[k], u);

for (int k=L[i.first]; k<R[i.first]; k++)

d[dis[V[k]]] = max(d[dis[V[k]]], h[V[k]]);// 字母集合达到的最大深度

}

if (!f)

for (int i=L[u]; i<R[u]; i++) d[dis[V[i]]] = 0;

}

int main(){

//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

n=6;

//cin >> n;

int ar[8][2]={

1, 'c',

2, 'b',

1, 'c',

4, 'b',

1,'a'

};

for (int i=2,a; i<=n; i++){ 

char c; 

//cin >> a >> c;

a=ar[i-2][0];

c=ar[i-2][1];

adj[a].push_back(make_pair(i, c-'a'));

}

//h[1]=1;

dfs1(1);

dfs2(1, 1);

for (int i=1; i<=n; i++) cout << ans[i] << " "; cout << "\n";

return 0;

}