spoj 375. Query on a tree 【树链剖分--插点问线】

灰太狼 2022-08-10 12:47 94阅读 0赞

题目：[spoj 375. Query on a tree][]

题意：题意很清晰，就是给你一颗树，每两点之间有权值，然后改变一些权值，问一条路径上的最大值。

分析：入门题目，直接套树链模板

AC代码；

#include <cstdio>
    #include <algorithm>
    #include <iostream>
    #include <string.h>
    using namespace std;
    const int N = 10010;
    #define Del(a,b) memset(a,b,sizeof(a))
    struct Node
    {
        int b,next;
    };
    Node e[N*2];
    int tree[N];
    int zzz,n,z,edge,root,a,b,c;
    int d[N][3];
    int first[N],dep[N],w[N];  //dep 深度,w线段树中位置
    int fa[N],top[N],son[N],siz[N];
    //fa表示父亲 top：所在重链的顶端节点 son：与v在同一重链上v的儿子节点
    void add_Node(int a,int b,int c)
    {
        e[++edge].b = b;
        e[edge].next = first[a];
        first[a] = edge;
    }
    void dfs(int x)
    {
        siz[x] = 1;son[x] = 0;
        for(int i=first[x];i>0;i = e[i].next)
            if(e[i].b!=fa[x])
            {
                fa[e[i].b] = x;
                dep[e[i].b] = dep[x] + 1;
                dfs(e[i].b);
                if(siz[e[i].b]>siz[son[x]])//保存重儿子
                    son[x] = e[i].b;
                siz[x] += siz[e[i].b];
            }
    }
    void build_tree(int v,int tp) //节点 重链顶端节点
    {
        w[v] = ++z;top[v] = tp;
        if(son[v]!=0)
            build_tree(son[v],top[v]);
        for(int i = first[v];i>0;i = e[i].next)
        {
            if(e[i].b!=son[v] && e[i].b!=fa[v])
                build_tree(e[i].b,e[i].b);
        }
    }
    //1,1,z,w[d[i][1]],d[i][2]
    void update(int root,int l,int r,int loc,int x)
    {
        if(loc>r || l>loc)
            return ;
        if(l == r)
        {
            tree[root] = x;
            return ;
        }
        int mid = (l+r)/2,ls = root * 2,rs = ls+1;
        update(ls,l,mid,loc,x);
        update(rs,mid+1,r,loc,x);
        tree[root] = max(tree[ls] ,tree[rs]);
    }
    int maxi(int root, int lo, int hi, int l, int r)
    {
         if (l > hi || r < lo) return 0;
         if (l <= lo && hi <= r) return tree[root];
         int mid = (lo + hi) / 2, ls = root * 2, rs = ls + 1;
         return max(maxi(ls, lo, mid, l, r), maxi(rs, mid+1, hi, l, r));
    }
    
    inline int find(int va, int vb)
    {
         int f1 = top[va], f2 = top[vb], tmp = 0;
         while (f1 != f2)
         {
             //printf("va:%d vb:%d f1:%d f2:%d \n",va,vb,f1,f2);
               if (dep[f1] < dep[f2])
               { swap(f1, f2); swap(va, vb); }
               tmp = max(tmp, maxi(1, 1, z, w[f1], w[va]));
               //printf("%d\n",tmp);
               va = fa[f1]; f1 = top[va];
         }
         if (va == vb) return tmp;
         if (dep[va] > dep[vb]) swap(va, vb);
         return max(tmp, maxi(1, 1, z, w[son[va]], w[vb]));  //
    }
    void init()
    {
         scanf("%d", &n);
         root = (n + 1) / 2;
         fa[root] = z = dep[root] = edge = 0;
         memset(siz, 0, sizeof(siz));
         memset(first, 0, sizeof(first));
         memset(tree, 0, sizeof(tree));
         for (int i = 1; i < n; i++)
         {
             scanf("%d%d%d", &a, &b, &c);
             d[i][0] = a; d[i][1] = b; d[i][2] = c;
             add_Node(a, b, c);
             add_Node(b, a, c);
         }
         dfs(root);
         build_tree(root, root);    //
         for (int i = 1; i < n; i++)
         {
             if (dep[d[i][0]] > dep[d[i][1]]) swap(d[i][0], d[i][1]);
             update(1, 1, z, w[d[i][1]], d[i][2]);
         }
    }
    char ch[100];
    void work()
    {
         while(~scanf("%s",ch) && ch[0]!='D')
         {
             scanf("%d%d", &a, &b);
             if (ch[0] == 'Q')
                printf("%d\n", find(a, b));
            else
                update(1, 1, z, w[d[a][1]], b);
         }
    }
    
    int main()
    {
        freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            init();
            work();
        }
        return 0;
    }

[spoj 375. Query on a tree]: http://www.spoj.com/problems/QTREE/