Tree Chain Partitioning

中国人戳这里

Background

Tree chain partitioning means that cut a tree into several edges

Some definitions

Heavy son: the son with the most Subnodes.

Light son: other sons except heavy son.

Heavy edge: the edge between root and heavy son

Light edge: the edge between root and light son.

Heavy chain： the chain that is only made of heavy edges.

Several theories

Noumenon

The most important theory: every node going to root will go through at most logN light edges.

And several easy theory:

1. Every node is at most in a heavy chain

2. There is no intersection between heavy chains.

Provement

I don't want to spend ink proving the second and third theory c because we can prove it just by the definition of heavy edges.

I will just prove the first theory.

If a node go through a light edge, we can know that there are at least one subtree is bigger than it.

So, the number of subnodes will increase at least one time.

So, it is true that very node going to root will go through at most logN light sons or .heavy chains.

Algorithm core

Appearently, we will cut the tree into different heavy edges.

Pretreatment

Firsr, before we doing the main things, we should know the nodes belong to which heavy edges.

And to find each edge belongs to which edge, we should know the size of each subtree.

Of course, if we want to turn the tree to a line, you should find the dfs order.

It is true that you should dfs for two times.

And I think how to find them is easy.

So i just provide my code.

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int fa;// father
    int dep;// deep 
    int pos;// the heavy son 
    int heavy;// the orgin of heavy edge. 
    int size;// the size of subtree 
    int ds;//dfs order 
}tr[MAXN];
vector<int>vec[MAXN];
void dfs1(int now,int fa)// 我想知道我爹和我失散多年的重儿子 
{
    tr[now].size = 1;
    tr[now].dep = tr[fa].dep+1;
    int mx = 0 ;
    for(int i = 0;i < vec[now].size();i++)
    {
        if(vec[now][i] != fa)
        {
            dfs1(vec[now][i],now);    
            tr[now].size += tr[vec[now][i]].size;
            if(tr[vec[now][i]].size > mx)
            {
                mx = tr[vec[now][i]].size;
                tr[now].pos = vec[now][i];
            }
        }    
    } 
}
int tot = 0;
void dfs2(int now,int fa)
{
    tr[now].ds = ++ tot;
    if(tr[fa].pos == now) 
    {
        tr[now].heavy = tr[fa].heavy;
    }
    dfs2(tr[now].pos,now);
    for(int i = 0;i < vec[now].size();i++)
    { 
        if(vec[now][i] != fa && vec[now][i] != tr[now].pos)
        {
            dfs2(vec[now][i],now);
        }
    }
}

Linear Processing

Generally, the tree chain partitioning will use the segment tree.

And if it use the splay, it will be called Link Cut Tree.

And the operation of segment tree is that we will do a single point modification when we go through a light edge，

and a Interval modification when we go through a heavy chain.

About

The tree chain partitioning is not a complete algorithm, it is just a way to spend logN time dealing with tree by the method of line.