loj2497 [PA2017]Banany(动态淀粉质)-白红宇

loj2497 [PA2017]Banany(动态淀粉质)

阅读量：4342 次

发布时间：2019-06-07

本文共 5471 字，大约阅读时间需要 18 分钟。

给定一棵树，点有点权，边有边权，你每次修改一个点点权或者是修改一个边边权

你一开始在1号点，你每次改节点之后你需要移动到另一个节点，满足这个节点权值减去路径长度最大(下一次从这个节点移动)如果存在相同的收益，选编号最小的节点

你需要输出每次移动到的节点坐标

题解：

处理树上多条路径可以用动态淀粉质

考虑动态淀粉质，对于点分树上每个点开个线段树，下标为点分树子树中的节点，权值为这个点到子节点的收益，同时维护最大值的坐标

对于点权的修改，可以直接在点分树上暴力跳父亲

对于一条边的修改，考虑从这条边连接两个点中点分树上深度较浅的节点向上暴力跳父亲

假设当前我们跳的是 i，我们需要找x和y中哪个点在以 i 为根原树中深度最大，找那个深度大的点，发现这条边的更改影响的点恰好是这个深度较大的点的子树所以对于每个点分树子树，我们维护一个dfs序，开线段树时按照dfs序存储(注意判断下标还要按照原编号判断)，那么这个操作就是一个区间修改

查询时候还是暴力跳父亲，直接查询每个父亲中子树中除了这个点的最大值，就是一个区间查询

注意要减去父亲到这个点的距离，这个可以单点查询查出来

#include 
    
     #include 
     #include 
      
       using namespace std;int n, q, sum, rt, tot;long long val[100010], ltmp;                // 点权vector
       
        
         > out[100010];   // 假装它是链式前向星bool vis[100010];                           // 构建点分树用的临时数组，最后是trueint sz[100010][20];                         // i 在他的点分树深度为 j 的父亲的子树大小, 第二维 0 为构建点分树临时数组int maxw[100010];                           // 构建点分树的临时数组long long dist[100010];                     // 临时的距离数组int depth[100010];                          // 点分树深度int deep[100010][20];                       // i 在以它深度为 j 的点分树父亲为根时的深度int father[100010][20];                     // i 的深度为 j 的父亲int dfn[100010][20];                        // i 在他的点分树深度为 j 的父亲的dfnvector
         
           id[100010]; // 子树中对应的struct data { int pos, rt; long long val; } tree[10000010]; //线段树int lc[10000010], rc[10000010], segtot = 0, segrt[100010]; //左右儿子，每个点的线段树根long long lazy[10000010]; //线段树lazytagvoid chkmax(int &a, int b) { if (a < b) a = b; }data operator+(const data &a, const data &b){ if (a.val != b.val) return a.val > b.val ? a : b; if (a.rt == -1) return b; if (b.rt == -1) return a; return id[a.rt][a.pos - 1] < id[b.rt][b.pos - 1] ? a : b;}int build(int cl, int cr, int rt){ int x = ++segtot; if (cl != cr) { int mid = (cl + cr) / 2; lc[x] = build(cl, mid, rt), rc[x] = build(mid + 1, cr, rt), tree[x] = tree[lc[x]] + tree[rc[x]]; } else tree[x].pos = cl, tree[x].rt = rt; return x;}void pushdown(int x){ tree[lc[x]].val += lazy[x], tree[rc[x]].val += lazy[x]; lazy[lc[x]] += lazy[x], lazy[rc[x]] += lazy[x], lazy[x] = 0;}void chenge(int x, int cl, int cr, int L, int R, long long val){ if (L <= cl && cr <= R) { tree[x].val += val, lazy[x] += val; return; } pushdown(x); int mid = (cl + cr) / 2; if (L <= mid) chenge(lc[x], cl, mid, L, R, val); if (R > mid) chenge(rc[x], mid + 1, cr, L, R, val); tree[x] = tree[lc[x]] + tree[rc[x]];}data chuans(int x, int cl, int cr, int L, int R){ if (L > R) return (data){0, -1, -9223372036854775807LL}; if (L <= cl && cr <= R) return tree[x]; pushdown(x); int mid = (cl + cr) / 2; if (R <= mid) return chuans(lc[x], cl, mid, L, R); if (L > mid) return chuans(rc[x], mid + 1, cr, L, R); return chuans(lc[x], cl, mid, L, R) + chuans(rc[x], mid + 1, cr, L, R);}void getrt(int x, int fa){ sz[x][0] = 1, maxw[x] = 0; for (pair
          
            i : out[x]) if (fa != i.first && vis[i.first] == false) getrt(i.first, x), sz[x][0] += sz[i.first][0], chkmax(maxw[x], sz[i.first][0]); chkmax(maxw[x], sum - sz[x][0]); if (maxw[x] < maxw[rt]) rt = x;}void getsz(int x, int fa, int rt){ sz[x][depth[rt]] = 1, father[x][depth[rt]] = rt, dfn[x][depth[rt]] = ++tot, id[rt].push_back(x); for (pair
           
             i : out[x]) if (fa != i.first && vis[i.first] == false) getsz(i.first, x, rt), sz[x][depth[rt]] += sz[i.first][depth[rt]];}void getdis(int x, int fa, int rt){ chenge(segrt[rt], 1, sz[rt][depth[rt]], dfn[x][depth[rt]], dfn[x][depth[rt]], val[x] - dist[x]); for (pair
            
              i : out[x]) if (fa != i.first && vis[i.first] == false) dist[i.first] = dist[x] + i.second, deep[i.first][depth[rt]] = deep[x][depth[rt]] + 1, getdis(i.first, x, rt);}void solve(int x, int d){ vis[x] = true, depth[x] = d, tot = 0, getsz(x, 0, x); segrt[x] = build(1, sz[x][depth[x]], x), dist[x] = 0, deep[x][depth[x]] = 0, getdis(x, 0, x); for (pair
             
               i : out[x]) if (vis[i.first] == false) sum = sz[i.first][depth[x]], rt = 0, getrt(i.first, 0), solve(rt, d + 1);}int main(){ map
              
               
                , long long> e; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%lld", &val[i]); for (int x, y, i = 1; i < n; i++) { scanf("%d%d%lld", &x, &y, &ltmp); out[x].push_back(make_pair(y, ltmp)); out[y].push_back(make_pair(x, ltmp)); if (x > y) swap(x, y); e[make_pair(x, y)] = ltmp; } maxw[0] = sum = n, getrt(1, 0), solve(rt, 1); int pos = 1; for (int opt, x, y, t = 1; t <= q; t++) { scanf("%d", &opt); if (opt == 1) { scanf("%d%lld", &x, &ltmp); for (int i = x; i != 0; i = father[i][depth[i] - 1]) chenge(segrt[i], 1, sz[i][depth[i]], dfn[x][depth[i]], dfn[x][depth[i]], ltmp - val[x]); val[x] = ltmp; } if (opt == 2) { scanf("%d%d%lld", &x, &y, &ltmp); if (x > y) swap(x, y); long long delta = ltmp - e[make_pair(x, y)]; e[make_pair(x, y)] = ltmp; if (depth[x] < depth[y]) swap(x, y); for (int i = y; i != 0; i = father[i][depth[i] - 1]) { if (deep[y][depth[i]] > deep[x][depth[i]]) { swap(x, y); } chenge(segrt[i], 1, sz[i][depth[i]], dfn[x][depth[i]], dfn[x][depth[i]] + sz[x][depth[i]] - 1, -delta); } } data ans = (data){0, -1, -9223372036854775807LL}; for (int i = pos; i > 0; i = father[i][depth[i] - 1]) { data tmp = chuans(segrt[i], 1, sz[i][depth[i]], 1, dfn[pos][depth[i]] - 1) + chuans(segrt[i], 1, sz[i][depth[i]], dfn[pos][depth[i]] + 1, sz[i][depth[i]]); tmp.val += chuans(segrt[i], 1, sz[i][depth[i]], dfn[pos][depth[i]], dfn[pos][depth[i]]).val - val[pos]; ans = ans + tmp; } printf("%d%c", pos = id[ans.rt][ans.pos - 1], t == q ? '\n' : ' '); } return 0;}

转载于:https://www.cnblogs.com/oier/p/10638889.html

你可能感兴趣的文章