[HDU 5029] Relief grain （树链剖分+线段树）

本文主要是介绍[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<0?(-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=1e5+10;
int N,M;
int edge[2*maxn][3];
int last[maxn];int dfst;
int dept[maxn],size[maxn],fath[maxn],bson[maxn],ntop[maxn],dfsn[maxn];stnode segt[4*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=0;CLR(last);CLR(dept);CLR(size);CLR(fath);CLR(bson);CLR(ntop);CLR(dfsn);CLR(ans);for(int i=1; i<N; i++){int u,v;scanf("%d%d", &u, &v);adde(u,v,i);adde(v,u,i+N);}dfs1(1);dfs2(1,1);build(1,1,maxn);for(int i=1; i<maxn; i++){pre[i].clear();suf[i].clear();}for(int i=1; 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]+1].push_back(c);v=fath[ntop[v]];}if(dept[u]>dept[v]) swap(u,v);pre[dfsn[u]].push_back(c);suf[dfsn[v]+1].push_back(c);}for(int i=1; i<=N; i++){for(int j=pre[i].size()-1; j>=0; j--){update(1,pre[i][j],1);}for(int j=suf[i].size()-1; j>=0; j--){update(1,suf[i][j],-1);}if(!segt[1].tmax) ans[i]=0;else ans[i]=segt[1].type;}for(int i=1; i<=N; i++){printf("%d\n", ans[dfsn[i]]);}}return 0;
}void adde(int u, int v, int i)
{edge[i][0]=u;edge[i][1]=v;edge[i][2]=last[u];last[u]=i;
}void dfs1(int u)
{size[u]=1;int tmax=-1;for(int e=last[u]; e; e=edge[e][2]){int v=edge[e][1];if(v==fath[u]) continue;dept[v]=dept[u]+1;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][2]){int v=edge[e][1];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=0;if(nl==nr){now.type=nl;return;}int mid=(nl+nr)>>1;build(np*2,nl,mid);build(np*2+1,mid+1,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)>>1;if(ql<=mid) update(np*2,ql,val);else update(np*2+1,ql,val);maintain(np);
}void maintain(int np)
{stnode &now=segt[np];stnode &lson=segt[np*2];stnode &rson=segt[np*2+1];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;}
}