Pathwalks CodeForces - 960F(主席树 || 树状数组)

2021-06-22 20:04

阅读：404

标签：cin 解析 class wal namespace code bsp int 最小

题意：

　　求树上最长上升路径

解析：

　　树状数组版：

　　　　edge[u][w] 代表以u为一条路的终点的小于w的最长路径的路的条数

·　　　　那么edge[v][w] = max(edge[u][w-1]) + 1;

因为w最小是0 所以所有的w都+1

主席树版待定

#include using namespace std;
const int maxn = 1e6+10, INF = 0x7fffffff;
int n, m, maxx = -INF;
mapint, int> edge[maxn];
int lowbit(int x)
{
    return x & -x;
}
int qp(int u, int w)
{
    int ret = 0;
    for(int i=w; i>0; i-=lowbit(i))
        ret = max(ret, edge[u][i]);
    return ret;
}

int build(int u, int w, int ans)
{
    while(w)
    {
        edge[u][w] = max(edge[u][w], ans);
        w += lowbit(w);
    }

}

int main()
{
    int u, v, w;
    cin >> n >> m;
    for(int i=0; i)
    {
        cin >> u >> v >> w;
        maxx = max(maxx, w);
        build(v, +1, qp(u, w)+1);
    }
    int max_ret = -INF;
    for(int i=1; i)
        max_ret = max(max_ret, qp(i, 100001));
    cout  endl;


    return 0;
}

Pathwalks CodeForces - 960F(主席树 || 树状数组)

标签：cin 解析 class wal namespace code bsp int 最小

原文地址：https://www.cnblogs.com/WTSRUVF/p/9678125.html

上一篇：python - 进程

下一篇：（九）排序（选择、插入、希尔）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Pathwalks CodeForces - 960F(主席树 || 树状数组)
文章链接：http://soscw.com/index.php/essay/97520.html

亲，登录后才可以留言！

Pathwalks CodeForces - 960F(主席树 || 树状数组)

评论

热门文章

推荐文章

最新文章

置顶文章