HDU 5029 Relief grain 樹鍊剖分 離線 線段樹

題意：給出一個樹。我們有以下操作：在節點u,v的路徑上，對所有節點加入一個給定種類的貨物。最後，對每個節點輸出該點數目最多的貨物的數量。

思路：看到樹上的路徑，是不是該想到樹鍊剖分呢？但是因為貨物的種類太多了，沒法狀态壓縮。 但是，因為相當于是離線查詢，我們是可以離線搞搞的。

           首先利用樹鍊剖分，利用差分的思想，打上标記。這樣，我們就可以從前往後根據重标号，從前往後遞推就可以了。

           然後，我們需要一個東西來維護兩個關鍵字，即：先比較貨物的數量，在貨物數量相同的時候，比較貨物的編号。用set就可以了。

代碼如下：

#pragma comment(linker,"/STACK:102400000,102400000")

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

const int MAX = 100100;

struct event{
    int po,va,ty;
    event(int p,int v,int t):po(p),va(v),ty(t){}
    bool operator < (const event & rhs) const{
        if(po != rhs.po) return po < rhs.po;
        else return ty > rhs.ty;
    }
};

struct point{
    int x, y;
    point(int xx, int yy):x(xx),y(yy){}
    bool operator < (const point & rhs) const{
        if(x != rhs.x) return x > rhs.x;
        else return y < rhs.y;
    }
};

vector<event> Event;
set<point> S;
int cnt[MAX];
int ans[MAX];
int N,M;
int x,y,z;
int head[MAX],nxt[MAX<<2],to[MAX<<2],tot;
int fa[MAX];//father of node
int top[MAX];//top node of every heavy chain
int deep[MAX];// deepth of every node
int num[MAX];// the number of node's children
int p[MAX];//new index of each node
int fp[MAX];//the node number of new index
int son[MAX];//heavy son of each node
int pos;// count of new index

void init()
{
    Event.clear();
    S.clear();
    tot = pos = 0;
    memset(head,-1,sizeof(head));
    memset(son,-1,sizeof(son));
    memset(cnt,0,sizeof(cnt));
}

void addedge(int u, int v)
{
    to[tot] = v; nxt[tot] = head[u];
    head[u] = tot++;
    to[tot] = u; nxt[tot] = head[v];
    head[v] = tot++;
}

void dfs1(int u,int pre,int d)
{
	deep[u] = d;fa[u] = pre;num[u] = 1;
	for(int i = head[u];i != -1; i = nxt[i])
	{
		int v = to[i];
		if(v != pre)
		{
			dfs1(v,u,d+1);
			num[u] += num[v];
			if(son[u] == -1 || num[v] > num[son[u]])
				son[u] = v;
		}
	}
}

void dfs2(int u, int sp)
{
    top[u] = sp; p[u] = pos++; fp[p[u]] = u;
    if(son[u] != -1){
        dfs2(son[u],sp);
        for(int i = head[u]; i != -1; i = nxt[i]){
            int v = to[i];
            if(v != son[u] && v != fa[u])
                dfs2(v,v);
        }
    }
}

//update of node of value
//the index of node is the
void update(int u, int v,int z)
{
    int f1 = top[u], f2 = top[v];
    while(f1 != f2){
        if(deep[f1] < deep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        Event.push_back(event(p[f1],z,1));
        Event.push_back(event(p[u]+1,z,-1));
        u = fa[f1]; f1 = top[u];
    }
    if(deep[u] > deep[v]) swap(u,v);
    Event.push_back(event(p[u],z,1));
    Event.push_back(event(p[v]+1,z,-1));
}

void erase(int ty)
{
    set<point>::iterator it = S.find(point(cnt[ty],ty));
    if(it != S.end()) S.erase(it);
    if(cnt[ty]) cnt[ty]--;
    if(cnt[ty]) S.insert(point(cnt[ty],ty));
}

void insert(int ty)
{
    set<point>::iterator it = S.find(point(cnt[ty],ty));
    if(it != S.end()) S.erase(it);
    cnt[ty]++;
    if(cnt[ty]) S.insert(point(cnt[ty],ty));
}

int main(void)
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d %d", &N, &M), N||M){
        init();
        for(int i = 0; i < N - 1; ++i){
            scanf("%d %d", &x,&y);
            addedge(x,y);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        for(int i = 0; i < M; ++i){
            scanf("%d %d %d", &x,&y,&z);
            update(x,y,z);
        }
        sort(Event.begin(),Event.end());
        for(int i = 0, sz = Event.size(),j = 0; i < pos; ++i){
            while(j < sz && Event[j].po <= i){
                if(Event[j].ty == -1) erase(Event[j].va);
                else insert(Event[j].va);
                ++j;
            }
            if(S.empty()) ans[i] = 0;
            else ans[i] = S.begin()->y;
        }
        for(int i = 1; i <= N; ++i)
            printf("%d\n",ans[p[i]]);
    }
    return 0;
}
           

第二種思路：

我們可以不偷懶，在樹鍊剖分的前提下，用線段樹來求解。

開始的步驟一樣，我們首先對剖分後的區間打标記。

然後，我們建立線段樹。在這道題中的線段樹是儲存的：在目前樹上的節點下，各個種類貨物的數量。對于每個線段樹的節點，儲存的是，對應貨物編号區間的數量的最大值。 

然後，對于原來樹上的節點，我們從前向後遞推，把對應的标記加入線段樹中。查詢最大的數量和對應的編号，我們從上往下盡可能的，向下向左走（最小的編号），同時保證該區間的最大值為整個區間上的最大值。

代碼可見：http://blog.csdn.net/u013368721/article/details/39449273