[HDU 5029] Relief grain （樹鍊剖分+線段樹）

HDU - 5029

其實這道題最大的難點不是樹鍊剖分，而是怎麼維護某個點被那些顔色染過，染過多少次

如果線上段樹維護的話，很難做到，估計得樹套樹，而且空間會炸

好在這題是離線的，可以使用差分的思想來維護

對一段區間[l,r]染色 c，相當于在這段區間左端點 l打上 c标志，右端點 r+1打上 -c标志

然後掃一遍整個區間 （依照 dfs序掃一遍整棵樹），期間不斷維護一顆線段樹

線段樹節點 [l,r] 維護的目前節點，顔色編号 cl - cr 之間染色最多的是哪個顔色，染了多少次

如果碰到 c 開始染色的标志，那麼線段樹節點[cl,cl]的 tmax+1，碰到結束染色的标志 [cl,cl]的 tmax-1

是以這題線段樹其實維護的并不是樹剖後形成的線性區間，而是在掃這個區間的過程中顔色的變化情況

#if _WIN32||_WIN64
#define lld I64d
#define llu I64u
#endif
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<?(-a):a;}
void swap(int& u, int &v){u^=v;v^=u;u^=v;}

struct stnode
{
    int l,r,tmax,type;
    void pri(){printf("l:%d r:%d tmax:%d type:%d\n", l, r, tmax, type);}
};
const int maxn=+;
int N,M;
int edge[*maxn][];
int last[maxn];

int dfst;
int dept[maxn],size[maxn],fath[maxn],bson[maxn],ntop[maxn],dfsn[maxn];

stnode segt[*maxn];
vector<int> pre[maxn],suf[maxn];

int ans[maxn];

void adde(int,int,int);
void dfs1(int);
void dfs2(int,int);


void build(int,int,int);
void update(int,int,int);
void maintain(int);

int main()
{
    while(~scanf("%d%d", &N, &M)&&N)
    {
        dfst=;
        CLR(last);
        CLR(dept);CLR(size);CLR(fath);CLR(bson);CLR(ntop);CLR(dfsn);
        CLR(ans);
        for(int i=; i<N; i++)
        {
            int u,v;
            scanf("%d%d", &u, &v);
            adde(u,v,i);adde(v,u,i+N);
        }
        dfs1();
        dfs2(,);
        build(,,maxn);
        for(int i=; i<maxn; i++)
        {
            pre[i].clear();
            suf[i].clear();
        }
        for(int i=; i<=M; i++)
        {
            int u,v,c;
            scanf("%d%d%d", &u, &v, &c);
            while(ntop[u]!=ntop[v])
            {
                if(dept[ntop[u]]>dept[ntop[v]]) swap(u,v);
                pre[dfsn[ntop[v]]].push_back(c);
                suf[dfsn[v]+].push_back(c);
                v=fath[ntop[v]];
            }
            if(dept[u]>dept[v]) swap(u,v);
            pre[dfsn[u]].push_back(c);
            suf[dfsn[v]+].push_back(c);
        }
        for(int i=; i<=N; i++)
        {
            for(int j=pre[i].size()-; j>=; j--)
            {
                update(,pre[i][j],);
            }
            for(int j=suf[i].size()-; j>=; j--)
            {
                update(,suf[i][j],-);
            }
            if(!segt[].tmax) ans[i]=;
            else ans[i]=segt[].type;
        }
        for(int i=; i<=N; i++)
        {
            printf("%d\n", ans[dfsn[i]]);
        }
    }
    return ;
}

void adde(int u, int v, int i)
{
    edge[i][]=u;
    edge[i][]=v;
    edge[i][]=last[u];
    last[u]=i;
}

void dfs1(int u)
{
    size[u]=;
    int tmax=-;
    for(int e=last[u]; e; e=edge[e][])
    {
        int v=edge[e][];
        if(v==fath[u]) continue;
        dept[v]=dept[u]+;
        fath[v]=u;
        dfs1(v);
        if(size[v]>tmax)
        {
            tmax=size[v];
            bson[u]=v;
        }
        size[u]+=size[v];
    }
}

void dfs2(int u, int top)
{
    dfsn[u]=++dfst;
    ntop[u]=top;
    if(!bson[u]) return;
    dfs2(bson[u],top);
    for(int e=last[u]; e; e=edge[e][])
    {
        int v=edge[e][];
        if(v==fath[u]||v==bson[u]) continue;
        dfs2(v,v);
    }
}

void build(int np,int nl,int nr)
{
    stnode &now=segt[np];
    now.l=nl;
    now.r=nr;
    now.tmax=;
    if(nl==nr){now.type=nl;return;}
    int mid=(nl+nr)>>;
    build(np*,nl,mid);
    build(np*+,mid+,nr);
}

void update(int np, int ql, int val)
{
    stnode &now=segt[np];
    if(now.l==now.r)
    {
        now.tmax+=val;
        return;
    }
    int mid=(now.l+now.r)>>;
    if(ql<=mid) update(np*,ql,val);
    else update(np*+,ql,val);
    maintain(np);
}

void maintain(int np)
{
    stnode &now=segt[np];
    stnode &lson=segt[np*];
    stnode &rson=segt[np*+];
    if(lson.tmax==rson.tmax)
    {
        now.tmax=lson.tmax;
        now.type=minn(lson.type,rson.type);
    }
    else if(lson.tmax>rson.tmax)
    {
        now.tmax=lson.tmax;
        now.type=lson.type;
    }
    else
    {
        now.tmax=rson.tmax;
        now.type=rson.type;
    }
}