频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 4366 树转化为连续序列 线段树
2012-08-15 15:55:52           
收藏   我要投稿

本题给的是一棵树。 然后找子孙中能力值大于父节点并且忠诚最高的。

由于树的结构不好搞线段树,所以要映射到一个连续序列上搞,把这个结点的子树都能映射到一个连续区间上就好办了。

很常见的套路就是DFS时间戳,记录进入结点的时间戳和出结点的时间戳,两个时间戳之间的都是这个结点的子孙结点了。

而我们要找能力值大于父节点的还得是忠诚最高的。两个限制。

那就进行排序,按能力值从高到低排,然后按排序后的顺序,对每个结点,先查询子树中的最大忠诚的结点,然后再更新。这样就能保证查到的一定是能力值大于父节点的结点了

并且题目告诉我们忠诚值互不相同,那么就省去了我们一些麻烦了。因为每个忠诚值必然对应一个唯一的序号,那么开个 map映射一下好了。


[cpp]
#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <string>  
#include <cstdio>  
#include <cmath>  
#include <queue>  
#include <map>  
#include <set>  
#define eps 1e-5  
#define MAXN 55555  
#define MAXM 111111  
#define INF 1000000007  
#define lch(x) x<<1  
#define rch(x) x<<1|1  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
using namespace std; 
int n, m; 
struct P 

    int id, a, l; 
    bool operator <(const P &t)const 
    { 
        return a > t.a; 
    } 
}p[MAXN]; 
struct EDGE 

    int v, next; 
}edge[MAXM]; 
int head[MAXN], e; 
int index, lf[MAXN], rf[MAXN]; 
int mx[4 * MAXN], ans[MAXN]; 
void init() 

    memset(head, -1, sizeof(head)); 
    memset(ans, -1, sizeof(ans)); 
    e = 0; 
    index = 0; 
    for(int i = 0; i <= 4 * n; i++) mx[i] = -1; 

void add(int x, int y) 

    edge[e].v = y; 
    edge[e].next = head[x]; 
    head[x] = e++; 

void dfs(int u) 

    lf[u] = index++; 
    for(int i = head[u]; i != -1; i = edge[i].next) 
        dfs(edge[i].v); 
    rf[u] = index; 

void up(int rt) 

    mx[rt] = mx[lch(rt)] > mx[rch(rt)] ? mx[lch(rt)] : mx[rch(rt)]; 

void update(int pos, int v, int l, int r, int rt) 

    if(l == r) {mx[rt] = v; return;} 
    int m = (l + r) >> 1; 
    if(pos <= m) update(pos, v, lson); 
    else update(pos, v, rson); 
    up(rt); 

int query(int L, int R, int l, int r, int rt) 

    if(L > R) return -1; 
    if(L <= l && R >= r) return mx[rt]; 
    int ret = -1; 
    int m = (l + r) >> 1; 
    if(L <= m) ret = max(ret, query(L, R, lson)); 
    if(m < R) ret = max(ret, query(L, R, rson)); 
    return ret; 

int main() 

    int T; 
    scanf("%d", &T); 
    while(T--) 
    { 
        int x; 
        scanf("%d%d", &n, &m); 
        init(); 
        map<int, int>mp; 
        for(int i = 1; i < n; i++) 
        { 
            scanf("%d%d%d", &x, &p[i].l, &p[i].a); 
            p[i].id = i; 
            mp[p[i].l] = i; 
            add(x, i); 
        } 
        sort(p + 1, p + n); 
        dfs(0); 
        for(int i = 1; i < n;) 
        { 
            int pos = i; 
            while(pos < n && p[pos].a == p[i].a) 
            { 
                int id = p[pos].id; 
                int tmp = query(lf[id] + 1, rf[id] - 1, 0, index - 1, 1); 
                if(tmp == -1) ans[id] = -1; 
                else ans[id] = mp[tmp]; 
                pos++; 
            } 
            pos = i; 
            while(pos < n && p[pos].a == p[i].a) 
            { 
                int id = p[pos].id; 
                update(lf[id], p[pos].l, 0, index - 1, 1); 
                pos++; 
            } 
            i = pos; 
        } 
        while(m--) 
        { 
            scanf("%d", &x); 
            printf("%d\n", ans[x]); 
        } 
    } 
    return 0; 


作者:sdj222555
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 序列
上一篇:HDU 1588 Gauss Fibonacci 矩阵
下一篇: Codeforces Round #133 (Div. 2)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站