K - Russian Dolls on the Christmas Tree
题意略过。
使用树上启发式合并(DSU on tree)。时间复杂度
启发式如下
加入点的时候检查左边和右边点是否存在
如果都存在，则
如果都不存在，则
其他情况，则答案不变。
树上启发式合并 其实是暴力法的优化，利用树剖中分重轻节点的思想，每次都让轻儿子回溯。
树链剖分还可以用于求最近公共祖先，常数极小。普通倍增方法的常数带个 或者
的常数。
代码如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN = 2e5+7;
const int MAXM = 2e5+7;
int Max(int a,int b){
return a>b?a:b;
}
struct Edge{
int v,next;
}e[MAXM*2];
int n,q,t;
int dfn[MAXN];
int hson[MAXN];
int top[MAXN];//每个节点所属的链
int dep[MAXN];//节点的深度
int fa[MAXN];//节点的父亲
int siz[MAXN];//每个节点，包括其子树的节点的数量
int rnk[MAXN];//每个节点再DFN中的位置
int L[MAXN],R[MAXN];//L = rnk R = rnk[now.fa.nextSon]-1;
int head[MAXN];int cnt;
int sum[MAXN];//表示从链头到i的前缀和
bool ccnt[MAXN];
int ans[MAXN];
int atot;
int tot;//dfn游标
void addEdge(int u,int v){
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
void add(int nd){
ccnt[nd] = true;
if(ccnt[nd-1] && ccnt[nd+1]){
atot--;
return;
}
if(!ccnt[nd-1] && !ccnt[nd+1]){
atot++;
return;
}
}
void del(int nd){
ccnt[nd] = false;
if(ccnt[nd-1] && ccnt[nd+1]){
atot++;
return;
}
if(!ccnt[nd-1] && !ccnt[nd+1]){
atot--;
return;
}
}
void init(){
memset(dfn,0,sizeof(dfn));
memset(hson,0,sizeof(hson));
memset(dep,0,sizeof(dep));
memset(fa,0,sizeof(fa));
memset(rnk,0,sizeof(rnk));
memset(top,0,sizeof(top));
memset(head,0,sizeof(head));
memset(siz,0,sizeof(siz));
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
memset(ccnt,0,sizeof(ccnt));
cnt = 1;
tot = 0;
atot = 0;
dep[1] = 1;
}
void dfs1(int now,int pre){
fa[now] = pre;
dep[now] = dep[pre]+1;
for(int k=head[now];k;k=e[k].next){
if(e[k].v == pre) continue;
dfs1(e[k].v,now);
siz[now] += siz[e[k].v];
siz[hson[now]] = (siz[e[k].v] > siz[hson[now]])?(hson[now]=e[k].v,siz[e[k].v]):(siz[hson[now]]);
}
siz[now] += 1;
}
void dfs2(int now,int tp){
top[now] = tp;
dfn[++tot] = now;
rnk[now] = tot;
L[now] = tot;
if(hson[now] != 0){
dfs2(hson[now],tp);
for(int k = head[now];k;k=e[k].next){
if(e[k].v == fa[now]) continue;
if(e[k].v != hson[now]){
dfs2(e[k].v,e[k].v);
}
}
}
R[now] = tot;
}
void dfs3(int now,bool keep){
for(int k=head[now];k;k=e[k].next){
if(e[k].v == fa[now] || e[k].v == hson[now]){
continue;
}
dfs3(e[k].v,false);
}
if(hson[now] != 0){
dfs3(hson[now],true);
}
for(int k=head[now];k;k=e[k].next){
if(e[k].v != hson[now] && e[k].v != fa[now]){
for(int i=L[e[k].v];i<=R[e[k].v];i++){
add(dfn[i]);
}
}
}
add(now);
ans[now] = atot;
if(!keep){
for(int i=L[now];i<=R[now];i++){
del(dfn[i]);
}
}
}
void preP(){
int pre = -1;
for(int i=1;i<=n;i++){
if(top[dfn[i]] != pre){
sum[i] = 0;
}else{
sum[i] = sum[i-1] + 1;
}
pre = top[dfn[i]];
}
}
int getDis(int x,int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[x] > dep[y]) swap(x,y);
ans += sum[rnk[y]];
y = fa[top[y]];
}
if(dep[x] > dep[y]) swap(x,y);
ans += sum[rnk[y]-rnk[x]];
return ans;
}
int getLCA(int x,int y){
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]){
x = fa[top[x]];
}else{
y = fa[top[y]];
}
}
return dep[x] > dep[y] ? y:x;
}
void ptTop(){
/*
打印dfn序号，以及对应点所在的链的链顶标号，查看树剖是否正确
*/
for(int i=1;i<=n;i++){
cout << dfn[i] << " " << top[dfn[i]] << endl;
}
}
int main(void){
cin >> t;
int _ = 0;
while(t--){
cin >> n;
_++;
init();
int u,v;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);addEdge(v,u);
}
dfs1(1,0);
dfs2(1,1);
dfs3(1,false);
printf("Case #%d:",_);
for(int i=1;i<=n;i++){
printf(" %d",ans[i]);
}
printf("\n");
}
return 0;
}
