BZOJ 3307 雨天的尾巴

Link

总算明白了大神们口中说的“剖完之后套用链上做法”的方法了。。。

Solution

要对链加标记算前缀和，要想办法转化成序列的问题。然而普通的DFS序可能会把路径弄成很多段，这不好。如果用树链剖分剖出的DFS序，一个路径在DFS序上最多$O(\log n)$段，就好了。

Code

#include "lucida"
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
using std::lower_bound;
using std::sort;
using std::unique;
using std::vector;
using std::swap;
using std::max;
const int MAXN=100000+11;
int nums[MAXN],nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
int dep[MAXN],sz[MAXN],prefer[MAXN],fa[MAXN],cht[MAXN];
void DFS(int pos) {
	sz[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(fa[pos]!=e->to) {
			int u=e->to;
			fa[u]=pos;
			dep[u]=dep[pos]+1;
			DFS(u);
			sz[pos]+=sz[u];
			if(sz[u]>sz[prefer[pos]])
				prefer[pos]=u;
		}
}
int dfn[MAXN],dfs[MAXN],dc;
void Assign(int pos) {
	dfs[++dc]=pos;
	dfn[pos]=dc;
	if(prefer[pos]) {
		cht[prefer[pos]]=cht[pos];
		Assign(prefer[pos]);
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=prefer[pos] && fa[pos]!=e->to) {
				cht[e->to]=e->to;
				Assign(e->to);
			}
	}
}
void Divide() {
	DFS(1);
	cht[1]=1;
	Assign(1);
}
struct Data {
	int cnt,id;
	Data(int cnt,int id):cnt(cnt),id(id){}
	bool operator <(const Data &a) const {
		return cnt==a.cnt?id>a.id:cnt<a.cnt;
	}
};
struct Tag {
	int v,cnt;
	Tag(int v,int cnt):v(v),cnt(cnt){}
};
vector<Tag> tag[MAXN];
void Modify(int p1,int p2,int c) {
	while(cht[p1]!=cht[p2]) {
		if(dep[cht[p1]]<dep[cht[p2]])
			swap(p1,p2);
		tag[dfn[cht[p1]]].push_back(Tag(c,1));
		tag[dfn[p1]+1].push_back(Tag(c,-1));
		p1=fa[cht[p1]];
	}
	if(dep[p1]>dep[p2])
		swap(p1,p2);
	tag[dfn[p1]].push_back(Tag(c,1));
	tag[dfn[p2]+1].push_back(Tag(c,-1));
}
namespace segtree {
	struct Node {
		Node *son[2];
		Data maxv;
		Node(Data maxv):maxv(maxv) {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN<<2);
			return Me++;
		}
		void Up() {
			maxv=max(son[0]->maxv,son[1]->maxv);
		}
	};
	struct SegTree {
		Node *root;
		int L,R;
		Node *operator ->() {
			return root;
		}
		/*
		operator Node *() {
			return root;
		} */
		void Build(Node *&pos,int L,int R) {
			pos=new Node(Data(0,L));
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int v) {
			if(L==R)
				pos->maxv.cnt+=v;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal,v);
				else
					Edit(pos->son[1],Mid+1,R,goal,v);
				pos->Up();
			}
		}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Edit(int pos,int v) {
			Edit(root,L,R,pos,v);
		}
	};
}using segtree::SegTree;
int main() {
	freopen("input","r",stdin);
	int n,m;
	is>>n>>m;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	Divide();
	static struct {int p1,p2,c;}op[MAXN];
	for(int i=1;i<=m;++i) {
		is>>op[i].p1>>op[i].p2>>op[i].c;
		nums[++nc]=op[i].c;
	}
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
	for(int i=1;i<=m;++i)
		Modify(op[i].p1,op[i].p2,ref(op[i].c));
	SegTree seg(1,nc);
	static int Ans[MAXN];
	for(int i=1;i<=n;++i) {
		for(vector<Tag>::iterator it=tag[i].begin();it!=tag[i].end();++it)
			seg.Edit(it->v,it->cnt);
		Ans[dfs[i]]=nums[seg->maxv.cnt==0?0:seg->maxv.id];		
	}
	for(int i=1;i<=n;++i)
		os<<Ans[i]<<'\n';
	return 0;
}