CF960F Pathwalks | 线段树优化DP

题目
设\(dp[x,w]\)为以结点\(x\)为结尾，且最后一条边边权为\(w\)的最长路径长度。
考虑根据顺序加边，对于边\((u,v)\)，更新

对于每个节点，建一棵线段树，维护\(dp[x]\)，这样每次更新\(dp[v,w]\)就相当于在\(dp[u]\)所对应的线段树中查询\([0,w - 1]\)的最大值（注意，左端点是0），并且将更新好的答案update到\(dp[v]\)所对应树中。
因为每个点都开一个线段树开不下，考虑动态开点。

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m; 
struct node
{
	int ls,rs,Max;
}T[N * 20];
int tot = 0;
int rt[N];
int maxl;
void update(int &root,int l,int r,int x,int d)
{
	if(!root) root = ++tot;
	if(l == r)
	{
		T[root].Max = max(T[root].Max,d);
		return;
	}
	int mid = (l + r) >> 1; 
	if(x <= mid) update(T[root].ls,l,mid,x,d);
	else update(T[root].rs,mid + 1,r,x,d);
	T[root].Max = max(T[T[root].ls].Max,T[T[root].rs].Max);
	return;
}
int query(int root,int l,int r,int s,int t)
{
	if(root == 0) return 0;
	if(l <= s && t <= r) return T[root].Max;
	int mid = (s + t) >> 1,ans = 0;
	if(l <= mid) ans = query(T[root].ls,l,r,s,mid);
	if(r > mid) ans = max(ans,query(T[root].rs,l,r,mid + 1,t));
	return ans;
}
int main(void)
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++)
	{
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		int cur = query(rt[u],0,w - 1,0,1e5) + 1; 
		maxl = max(maxl,cur);
		update(rt[v],0,1e5,w,cur);
	}
	printf("%d\n",maxl);
	return 0;
}