树剖求助
查看原帖
树剖求助
380653
zhangtang007楼主2021/10/6 20:53
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = (s <<1)+(s<<3) + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}
inline void write(int x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9)
		write(x/10);
    putchar(x%10+'0');
}
#define ls p<<1
#define rs p<<1|1
const int maxn = 2e5+10;
int n , m ;
vector<pair<int ,int > > ques;
struct G{
	int  t , next;
}edge[maxn << 1];
int head[maxn] , tot;
void add(int f , int t){
	edge[++tot] = G({t ,head[f]}),head[f] = tot;
}
int dfn[maxn] , siz[maxn],rnk[maxn],fa[maxn],son[maxn], top[maxn],dep[maxn];
int tim;
void dfs1(int node){
	siz[node] = 1; 
	for(int i = head[node] ; i ; i = edge[i].next){
		if(edge[i].t != fa[node]){
			dep[edge[i].t] = dep[node] + 1;
			fa[edge[i].t] = node;
			dfs1(edge[i].t);
			siz[node] += siz[edge[i].t];
			if(siz[edge[i].t] > siz[son[node]]) son[node] = edge[i].t;
		}
	}
}
void dfs2(int node ,int fno){
	dfn[node] = ++tim;
//	rnk[tim] = node;
	top[node] = fno;
	if(son[node] == 0) return ;
	dfs2(son[node] ,fno);
	for(int i = head[node]; i ; i=edge[i].next)
		if(edge[i].t != son[node] && edge[i].t != fa[node]) dfs2(edge[i].t , edge[i].t);
}
int tree[maxn << 2] , tag[maxn << 2];
inline void pushup(int p){
	tree[p] = min(tree[ls],tree[rs]);
}
void pushdown(int p){
	if(tag[p] != 0x3f3f3f3f){
		tree[ls] = min(tree[ls],tag[p]);
		tree[rs] = min(tree[rs],tag[p]);
		tag[ls] = min(tag[ls] ,tag[p]);
		tag[rs] = min(tag[rs] ,tag[p]);
		tag[p] = 0x3f3f3f3f;
	}
}
void update(int l, int r , int s ,int t , int k , int p){
	pushdown(p);
	if(s >= l && t <= r){
		tree[p] = min(tree[p] , k);
		tag[p] = min(tag[p] , k);
		return ;
	}
	int mid = s + t >> 1;
	if(l <= mid) update(l , r , s , mid, k , ls);
	if(r > mid) update(l , r , mid+1 , t , k , rs);
	pushup(p);
}
int getmin(int l , int r , int c , int p){
	pushdown(p);
	if(l == r) return tree[p];
	int mid = l + r >> 1;
	if( c <= mid ) return getmin(l ,mid , c, ls);
	else return getmin(mid + 1 , r , c , rs);
}
void adds(int u , int v, int dis){
	while(top[u]!=top[v]){
		if(dep[top[u]] < dep[top[v]]) swap(u ,v );
		update(1 , n , dfn[top[u]] , dfn[u], dis , 1);
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u , v);
	update(1 , n , dfn[u]+1 ,dfn[v] , dis , 1);
}

signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n- 1; ++i){
		int x ,y ;
		cin >>x >> y;
		add(x,y) ;
		add(y,x) ;
		ques.push_back(make_pair(x,y));
	}
	
//	dep[1] = 1;fa[1] = 0;
	dfs1(1) ; 
	dfs2(1 , 1);
	memset(tree , 0x3f3f3f3f , sizeof tree);
	memset(tag , 0x3f3f3f3f, sizeof tag);
	for(int i = 1; i <= m ; ++i){
		int x , y, z;
		cin >> x >> y >> z;
		adds(x ,y , z);
	}
	for(int i = 1; i <= n - 1; i++){
		int a = ques[i-1].first , b = ques[i-1].second;
		if(dep[a] > dep[b]) swap(a , b);
		int ans = getmin(1 , n , dfn[b] , 1);
		cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
	}
    return 0;
}



2021/10/6 20:53
加载中...