题目
设\(dp[x,w]\)为以结点\(x\)为结尾，且最后一条边边权为\(w\)的最长路径长度。
考虑根据顺序加边，对于边\((u,v)\)，更新
\[dp[v,w] = \max_{w' < w}\{dp[u,w']\} + 1
\]
对于每个节点，建一棵线段树，维护\(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;
}