Hdu 5029 Relief grain（樹鏈剖分）
題目大意：
給出一棵樹。
然後有m個操作，每個操作都在兩點的路徑上分配不同的糧食。
最後要求輸出所有村莊有的最多的糧食的種類。
思路分析：
一眼就看得出來是樹鏈剖分的題目。
現在的問題就是，每一次操作，如何維護每個點的最多的食物編號，以及最多的食物的數量。要記錄這兩個值是肯定的。
首先可以想到將所有的操作按照z排序。這樣每一回合操作，稱一回合為處理同一種顏色。一回合結束之後，後面的操作就不會影響前面取得的最大值。因為後面的操作的食物的種類不一樣，是不可以再繼續累加的。
然後可以發現一個規律，就是每處理完一種顏色之後，在線段樹上，顏色比這種顏色編號大的顏色都存在了這個節點的樹形結構的上面。也就是父親節點甚至是父親節點的父親節點。
所以我們就直接考慮pushdown部分吧，這是這道題目的難點。
假設操作只有 2 3 4這三種食物。
我們首先先處理完了所有食物種類為2的所有操作。
現在在處理種類為3的操作。如果這個操作的指定區間的lazy標記的顏色也是3.那麼就直接累加，毫無疑問。但是如果這個區間是2...由於我們現在還在處理3，你不確定後面還有多少種類為3的操作，所以我們就要將這個種類為2的lazy往下推（用遞歸的pushdown實現）。然後將3更新。
按照如上操作處理了3之後。
現在我們處理種類為4的。我們注意到之前說的規律。
2一定在3下面，那麼4的下面也之後有3.
所以現在種類4的操作，碰到了4.那麼也是直接累加無疑問。好，如果碰到操作三，按照我們上述的，要將3pushdown。但是，在pushdown3的過程中，這個3又會遇到lazy顏色為2的。產生沖突。但是我們注意到，如果是4將3推下去，而且3又碰到了2，也就以為著，這個子樹只有一個節點的lazy是3了。為什麼，還是那個規律。自己想一下就明白。
所以意思就是下面不會有三，那個節點的全部三就是所有操作的全部三。當遞推下的3的數量比碰到的那個2的數量還要小，也就意味著以下的節點的答案不可能是3 的。
但是如果2比三小，可能這下面還有一些2沒有累加，所以就把2遞推下去，再遞推3下去，再更新4.
好，現在我們分析時間復雜度。
首先m此操作。
然後查找熟練logn
線段樹更新logn
那麼這個pushdown的遞歸呢。
因為遞歸層數是不會超過logn的。
所以最多也就是 m*log^3...
當然最優解肯定不是這個。。。
#include
#include
#include
#include
#include
#pragma comment(linker,"/STACk:10240000,10240000")
#define maxn 100005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
int next[maxn<<1],to[maxn<<1],head[maxn],tot;//臨界表
int pre[maxn],root[maxn],siz[maxn],son[maxn],w[maxn],dep[maxn],id;//原樹的父親 鏈上的根 siz 有最大siz的子樹 重新分配的id 深度 getid中來計數的
pairans[maxn<<2];//線段樹變量
paircov[maxn<<2];
int n,cur;
void init()
{
pre[1]=0;
dep[1]=0;
tot=0;id=0;
memset(head,0,sizeof head);
}
void addedge(int u,int v)
{
tot++;
next[tot]=head[u];
to[tot]=v;
head[u]=tot;
}
void dfs(int now)//to get size,son,dep,pre...
{
son[now]=0;
siz[now]=1;
for(int p =head[now]; p ; p=next[p])
{
int t=to[p];
if(t!=pre[now])
{
pre[t]=now;
dep[t]=dep[now]+1;
dfs(t);
if(siz[t]>siz[son[now]])son[now]=t;
siz[now]+=siz[t];
}
}
}
void getid(int now,int rt)//to get w and root...
{
w[now]=++id;
root[now]=rt;
if(son[now])getid(son[now],rt);
for(int p = head[now] ; p ; p=next[p])
{
int t=to[p];
if(t!=son[now]&&t!=pre[now])
getid(t,t);
}
}
void pushdown(int num,int s,int e)
{
if(s==e)
{
cov[num].first=cov[num].second=0;
return;
}
if(cov[num].second)
{
if(cov[num<<1].second==cov[num].second)
cov[num<<1].first+=cov[num].first;
else
{
if(cov[num<<1].firstans[num<<1].first)
ans[num<<1]=cov[num<<1];
}
if(cov[num<<1|1].second==cov[num].second)
cov[num<<1|1].first+=cov[num].first;
else
{
if(cov[num<<1|1].firstans[num<<1|1].first)
ans[num<<1|1]=cov[num<<1|1];
}
cov[num].first=cov[num].second=0;
}
}
void build(int num,int s,int e)
{
ans[num].first=ans[num].second=0;
cov[num].first=0;
cov[num].second=0;
if(s==e)return;
build(lson);
build(rson);
}
void update(int num,int s,int e,int l,int r,int val)
{
if(l<=s && r>=e)
{
if(cov[num].second==val)
cov[num].first++;
else
{
pushdown(num,s,e);
cov[num].first++;
cov[num].second=val;
}
if(s==e){
if(cov[num].first>ans[num].first)
ans[num]=cov[num];
}
return;
}
pushdown(num,s,e);
if(l<=mid)update(lson,l,r,val);
if(r>mid)update(rson,l,r,val);
}
int query(int num,int s,int e,int pos)
{
if(s==e)return ans[num].second;
pushdown(num,s,e);
if(pos<=mid)return query(lson,pos);
else return query(rson,pos);
}
void work(int x,int y,int val)
{
while(root[x]!=root[y])
{
if(dep[root[x]]dep[y])swap(x,y);
update(1,1,n,w[x],w[y],val);
}
struct node
{
int x,y,z;
bool operator < (const node &cmp)const{
return z
