树形结构

阅读量：3952 次

发布时间：2019-05-24

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

文章目录

虚树

对于多次查询的问题，为了总复杂度只与查询点的数量有关，而不是和总点数有关。对信息进行浓缩。重新建虚树。

题意：每次给出m个关键点，求切断1号点到所有关键点的路径需要的最小花费。

思路：如果允许

O (n)

查询，这就是基础DP。虚树建立，通过维护右链实现。

#include
   
    using namespace std;//#define endl '\n'#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)typedef long long LL;using PII = pair
    
     ;const int N = 2.5e5 + 5;const LL mod = 1e9 + 7;const double eps = 1e-8;int n, m;vector
     
       G[N];vector
      
        H[N];int f[N][20], id[N], dep[N], sta[N], ct = 0, qery[N];LL minv[N];void dfs(int v, int p){
       f[v][0] = p;    for(int i = 1; i < 20; ++i)        f[v][i] = f[f[v][i-1]][i-1];    id[v] = ++ct;    dep[v] = dep[p] + 1;    for(PII pa : G[v]){
           int u = pa.first;        if(u == p)continue;        minv[u] = min(0ll + pa.second, minv[v]);        dfs(u, v);    }}int lca(int x, int y){
       if(dep[x] < dep[y])swap(x, y);    int d = dep[x] - dep[y];    for(int i = 0; i < 20; ++i){
           if(d & (1 << i))x = f[x][i];    }    if(x == y)return x;    for(int i = 19; i >= 0; --i){
           if(f[x][i] != f[y][i]){
               x = f[x][i];            y = f[y][i];        }    }    return f[x][0];}bool cmp(int u, int v){
       return id[u] < id[v];}LL getans(int v){
       LL sum = 0;    for(int u : H[v]){
           sum += getans(u);    }    H[v].clear(); // clear the graph    return qery[v] ? minv[v] : min(sum, minv[v]);}int main(){
       IOS;    cin >> n;    for(int u, v, w, i = 1; i < n; ++i){
           cin >> u >> v >> w;        G[u].emplace_back(v, w);        G[v].emplace_back(u, w);    }    minv[1] = 1e18;    dfs(1, 0);    int tt;    cin >> tt;    while(tt--){
           cin >> m;        vector
       
         v(m);        for(int i = 0; i < m; ++i){
               cin >> v[i];            qery[v[i]] = 1; // 标记查询点        }        sort(v.begin(), v.end(), cmp); // 按dfs序排序        int top = 1;        sta[top] = 1;// 栈维护右链        for(int i = 0; i < m; ++i){
               int lc = lca(sta[top], v[i]);            if(lc != sta[top]){
                   while(id[lc] < id[sta[top - 1]]){
                       H[sta[top - 1]].push_back(sta[top]);                    top--;                }                if(id[lc] > id[sta[top - 1]]){
    // LCA 在sta[top - 1]的下面                    H[lc].push_back(sta[top]); // LCA 与sta[top]连接                    sta[top] = lc; // lca入栈覆盖掉sta[top]                }else{
    // LCA == sta[top - 1]                    H[sta[top - 1]].push_back(sta[top]);                    top--;                }            }            sta[++top] = v[i];        }        for(int i = 1; i < top; ++i){
    // 右链加入图中            H[sta[i]].push_back(sta[i + 1]);        }        cout << getans(sta[1]) << endl;        for(int i = 0; i < m; ++i){
               qery[v[i]] = 0;        }    }}

点分治

点分治适合处理大规模的树上路径信息问题。

题意：给定一棵有 $n$ 个点的带点权树， $m$ 次询问，每次询问给出 $k$ ，询问树上距离为 $k$ 的点对是否存在。

#include
   
    using namespace std;//#define endl '\n'#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)typedef long long LL;using PII = pair
    
     ;const int N = 1e4 + 5, V = 1e7 + 5;vector
     
       G[N];int n, m, rt, cnt, masz, tot, que[105], ans[105], siz[N], dis[N], dd[N];/*rt当前子树的重心（最大子树最小）tot当前子树的大小*/bool vis[N], flag[V];void dfsize(int v, int p){
    // 找树跟，获得所有子树的大小    siz[v] = 1;    int ms = 0;    for(PII e : G[v]){
           if(e.first == p || vis[e.first])continue;        dfsize(e.first, v);        siz[v] += siz[e.first];        ms = max(ms, siz[e.first]);    }    ms = max(ms, tot - siz[v]);    if(masz > ms)masz = ms, rt = v;}void getdis(int v, int p){
    // 获得子树内的各点到rt的距离    dd[++cnt] = dis[v];    for(PII e : G[v]){
           if(e.first == p || vis[e.first])continue;        dis[e.first] = dis[v] + e.second;        getdis(e.first, v);    }}void dfs(int v){
    // 点分治    queue
      
        Q; // 记录flag数组为true的下标，用于清空    flag[0] = true;    vis[v] = true;    for(PII e : G[v]){
           if(vis[e.first])continue;        cnt = 0;        dis[e.first] = e.second;        getdis(e.first, v);        for(int j = 1; j <= cnt; ++j)            for(int k = 0; k < m; ++k)                if(que[k] >= dd[j])                    ans[k] |= flag[que[k] - dd[j]];        for(int j = 1; j <= cnt; ++j)            if(dd[j] < V)                flag[dd[j]] = true, Q.push(dd[j]);    }    while(!Q.empty())flag[Q.front()] = false, Q.pop();    for(PII e : G[v]){
           if(vis[e.first])continue;        masz = n;        tot = siz[e.first];        dfsize(e.first, 0);        dfsize(rt, 0);        dfs(rt);    }}int main(){
       IOS;    cin >> n >> m;    for(int u, v, w, i = 1; i < n; ++i){
           cin >> u >> v >> w;        G[u].emplace_back(v, w);        G[v].emplace_back(u, w);    }    for(int i = 0; i < m; ++i)        cin >> que[i];    masz = n;    tot = n;    dfsize(1, 0);    dfsize(rt, 0);    dfs(rt);    for(int i = 0; i < m; ++i)        cout << (ans[i] ? "AYE" : "NAY") << endl;}

题意： $\cdot 10^5$ 个点，求下式。

\sum_{u=1}^{n} \sum_{v=1}^{n} \min \left(a_{u}, a_{v}\right) \operatorname{dis}(u, v)

思路：点分治。每次统计经过树根的所有路径的贡献。但是这个统计很难实现。所以强制要求每两个点之间路径都经过根节点，再对于每个子树减去子树内的路径。通过对每个点的

{a[v], dis[v]\}

排序实现。

O(n\log^2 n)

#include 
   
    #define endl '\n'#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);#define fi first#define se secondusing namespace std;typedef long long LL;typedef pair
    
      PII;typedef pair
     
       PIII;const LL inf = 4e18;const double eps = 1e-10;const LL mod = 998244353;const int N = 2e5 + 50;int n, a[N];vector
      
        G[N];int rt, masz, totn, siz[N], vis[N], dis[N], ct = 0;LL ans = 0;PII dd[N];void dfs_root(int v, int fa){
       siz[v] = 1;    int maxsz = 0;    for(int u : G[v]){
           if(vis[u] || u == fa)continue;        dfs_root(u, v);        siz[v] += siz[u];        maxsz = max(siz[u], maxsz);    }    maxsz = max(maxsz, totn - siz[v]);    if(maxsz < masz) masz = maxsz, rt = v;}void dfs_dis(int v, int fa){
       dd[++ct] = {
   a[v], dis[v]};    for(int u : G[v]){
           if(u == fa || vis[u])continue;        dis[u] = dis[v] + 1;        dfs_dis(u, v);    }}LL calc(int v, int fa, bool flag){
       dis[v] = flag;    ct = 0;    dfs_dis(v, fa);    sort(dd + 1, dd + ct + 1);    LL res = 0, asum = 0, adsum = 0;    for(int i = 1; i <= ct; ++i){
           res = (res + asum * dd[i].second % mod + adsum) % mod;        asum = (asum + dd[i].first) % mod;        adsum = (adsum + dd[i].second * dd[i].first % mod) % mod;    }    return res;}void solve(int v){
       dfs_root(v, 0);    v = rt;    dfs_root(rt, 0);    ans = (ans + calc(rt, 0, 0)) % mod;    vis[v] = true;    for(int u : G[v]){
           if(vis[u])continue;        ans = (ans - calc(u, v, 1)) % mod;        masz = N;        totn = siz[u];        solve(u);    }}int main(){
       IOS;    cin >> n;    for(int i = 1; i <= n; ++i)        cin >> a[i];    for(int v, u, i = 1; i < n; ++i){
           cin >> v >> u;        G[v].push_back(u);        G[u].push_back(v);    }    masz = N;    totn = n;    solve(1);    ans = 2 * ans % mod;    cout << (ans + mod) % mod << endl;}

dsu on tree

树上启发式合并，其实是一个树版本的并查集。所以它的时间复杂度为 $\log n)$ 。解决的问题是在 $\log n)$ 的总时间复杂度下，找u子树中，有多少个点具有某种性质。

思想是维护一些全局的变量（数组），当dfs到u的时候，这些变量代表的是u子树的信息。当向上传递的时候，只有重儿子才会向上传递，轻儿子要把做的改变恢复（或者说清空，有时候清空比逆操作快）。

问题：求每个u子树下，颜色为c的点的数量。

该模板中，要先求出所有点的子树大小。dfs部分不需要修改，只需要修改add函数。

int cnt[maxn];bool big[maxn];void add(int v, int p, int x){
       cnt[ col[v] ] += x;    for(auto u: g[v])        if(u != p && !big[u])            add(u, v, x)}void dfs(int v, int p, bool keep){
       int mx = -1, bigChild = -1;    for(auto u : g[v])       if(u != p && sz[u] > mx)          mx = sz[u], bigChild = u;    for(auto u : g[v])        if(u != p && u != bigChild)            dfs(u, v, 0);  // run a dfs on small childs and clear them from cnt    if(bigChild != -1)        dfs(bigChild, v, 1), big[bigChild] = 1;  // bigChild marked as big and not cleared from cnt    add(v, p, 1);    //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily.    if(bigChild != -1)        big[bigChild] = 0;    if(keep == 0)        add(v, p, -1);}

题意：一颗有点权有根树，问u子树下数量最多的点权的和。

思想：每个点维护1、子树下所有点权的数量；2、子树下最大的点权数量；3、最多点权数量的点权和。

#include
   
    using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//#define endl '\n'typedef long long LL;const int N = 1e5 + 5;int n, c[N], siz[N], cnt[N], big[N];LL ans[N], sum = 0;int maxcnt = 0;vector
    
      G[N];void dfsize(int u, int fa){
       siz[u] = 1;    for(int v : G[u]){
           if(v == fa)continue;        dfsize(v, u);        siz[u] += siz[v];    }}void add(int u, int fa, int x){
       cnt[c[u]] += x;    if(cnt[c[u]] == maxcnt){
           sum += c[u];    }    else if(cnt[c[u]] > maxcnt){
           maxcnt = cnt[c[u]];        sum = c[u];    }    for(int v : G[u]){
           if(v != fa && !big[v])            add(v, u, x);    }}void dfs(int u, int fa, bool keep){
       int ms = 0, son = 0;    for(int v : G[u]){
           if(v == fa)continue;        if(siz[v] > ms){
               ms = siz[v];            son = v;        }    }    for(int v : G[u]){
           if(v == fa || v == son)continue;        dfs(v, u, 0);    }    if(son)dfs(son, u, 1), big[son] = 1;    add(u, fa, 1);    ans[u] = sum;    if(son)big[son] = 0;    if(!keep){
           add(u, fa, -1);        maxcnt = 0;        sum = 0;    }}int main(){
       IOS;    cin >> n;    for(int i = 1; i <= n; ++i){
           cin >> c[i];    }    for(int u, v, i = 1; i < n; ++i){
           cin >> u >> v;        G[u].push_back(v);        G[v].push_back(u);    }    dfsize(1, 0);    dfs(1, 0, 1);    for(int i = 1; i <= n; ++i){
           if(i != n)cout << ans[i] << " ";        else cout << ans[i] << endl;    }}

题意：一颗有根树，叶子结点具有权值，求每个子树下，叶子权重差的最小值。

思路：维护子树的叶子权重的一个map。插入时，查找前驱后继，更新最小权重差。

O(n\log^2 n)

题意：给一个森林。每个节点有一个名字，查询v子树下第k层中，不同的名字的数量。

思路：维护每一层的不同名字的set。查询直接输出nset[dep[v]+k].size()。

O(n\log^2 n)

树上背包

n+1个节点选m+1个节点，让权值之和最大。选子节点要先选父节点。

#include
   
    using namespace std;#define endl '\n'using ll = long long;using pii = pair
    
     ;const int maxn=1e5+3;const ll mod=1e9+7;vector
     
       G[305];int n,m,s[305];int f[305][305];void dfs(int x){
       f[x][1] = s[x];    for(int v : G[x]){
           dfs(v);        for(int i=m;i>1;--i){
               for(int j=i-1;j>0;--j)                f[x][i] = max(f[x][i],f[x][j]+f[v][i-j]);        }    }}int main(){
       ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    cin>>n>>m;    for(int v,ts,i=1;i<=n;++i){
           cin>>v>>s[i];        G[v].push_back(i);    }    m+=1;    dfs(0);    cout<
      
       <

DFS序+分层前缀和

给一棵树，每个节点有一个字母，多次查询（v h），问v节点的子树中从深度为h（1号节点为跟）的所有节点中字母可不可以组成回文串。

每一层可以用异或前缀和来存储字母个数奇偶性，任务转化为找v节点下第一个该层节点和最后一个该层节点

快速寻找的方式是记录进入子树in[v]和离开子树out[v]的DFS序，比in[v]大的第一个该层节点即为第一个节点，比out[v]小的第一个节点则为最后一个节点。

#include 
   
    using namespace std;#define pb push_back#define mp make_pairconst int maxn = 5e5 + 5;using pii = pair
    
     ;int pow2[32];int cnt = 0;char s[maxn];vector
     
       H[maxn];vector
      
        G[maxn];int in[maxn], out[maxn];void dfs(int u, int dep){
       in[u] = ++cnt;    H[dep].pb(mp(cnt, H[dep].back().second ^ pow2[s[u] - 'a']));    for(int son : G[u]){
           dfs(son, dep + 1);    }    out[u] = ++cnt;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    int n, q;    for(int i=0;i<32;++i){
           pow2[i] = 1 << i;    }    cin>>n>>q;    for(int i=1;i<=n;++i){
           H[i].resize(1);    }    for(int tf, i = 2; i <= n;++i){
           cin>>tf;        G[tf].pb(i);    }    cin>>(s+1);    dfs(1, 1);    int v, h, l, r;    while(q--){
           cin>>v>>h;        l = lower_bound(H[h].begin(), H[h].end(), mp(in[v], -1)) - H[h].begin() - 1;        r = lower_bound(H[h].begin(), H[h].end(), mp(out[v], -1)) - H[h].begin() - 1;        v = H[h][l].second ^ H[h][r].second;//        cout<<"*"<
       
        <<" "<
        
         <

DFS序+差分数组

题意：求合法的根（到所有点的路径上任意点权各不相同的根）的数量。

思路：若两点点权相同，则两点左右的点都一定是非法的。应该找到所有非法的点。

考虑一个点和它的某个子树的点有相同点权。如图， $1$ 的 $2$ 子树有相同点权点 $4$ ，则子树 $2$ 以外的所有点都是非法的。

考虑一个点和它的子树以外的点有相同点权。如图， $4$ 和非自己子树的 $1$ 相同，则 $4$ 的整个子树非法。

维护子树整体，和其他的部分之间的关系。DFS序是最好的方式。区间修改，采用差分数组。而判断子树内有无点相同，可以用实时统计的map。dfs前后统计，判断该权值的点数量变化。判断非子树是否存在相同点，则用全局的该权值点数减去子树下的点数判断。

#include
   
    #define endl '\n'#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;typedef long long LL;const int N = 2e5 + 5, mod = 1e9;int n, a[N], cnt, id[N], diff[N], siz[N];vector
    
      G[N];map
     
       now, all;void dfs(int u, int fa){
       siz[u] = 1;    id[u] = ++cnt;    ++now[a[u]];    for(int v : G[u]){
           if(v == fa)continue;        int x = now[a[u]], y = now[a[v]];        dfs(v, u);        siz[u] += siz[v];        if(x < now[a[u]]){
               // v子树下有相同，删除            ++diff[1];            --diff[id[v]];            ++diff[id[v] + siz[v]];        }        if(all[a[v]] - (now[a[v]] - y) > 0){
    // v子树以外有相同，删除子树            ++diff[id[v]];            --diff[id[v] + siz[v]];        }    }}int main(){
       IOS;    cin >> n;    for(int i = 1; i <= n; ++i){
           cin >> a[i];        ++all[a[i]];    }    for(int x, y, i = 1; i < n; ++i){
           cin >> x >> y;        G[x].pb(y);        G[y].pb(x);    }    dfs(1, 0);    int ans = 0;    for(int now = 0, i = 1; i <= n; ++i){
           now += diff[i];        if(!now)++ans;    }    cout << ans << endl;}

树链剖分（HLD）

通过重轻链剖分，把树放在线段树上维护，可以同时修改/查询一段路径or一颗子树。

在(u,v)路径上查询，修改。在v子树上进行查询、修改。

#include
   
    using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define endl '\n'#define fi first#define se second#define mp make_pair#define lson rt << 1, l, mid#define rson rt << 1|1, mid + 1, rtypedef long long LL;typedef pair
    
      PLI;const int N = 1e5 + 5;int n, m;LL p;vector
     
       G[N];int dfsid = 0;int top[N], son[N], sz[N], dep[N], id[N], fa[N];int w[N], wt[N];int tr[N << 2], lazy[N << 2];//----------------  segment tree  --------------------------void pushup(int rt){
       tr[rt] = (tr[rt << 1] + tr[rt << 1 | 1]) % p;}void pushdown(int rt, int l, int r){
       if(lazy[rt]){
           int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1;        lazy[ls] = (lazy[ls] + lazy[rt]) % p;        lazy[rs] = (lazy[rs] + lazy[rt]) % p;        tr[ls] = (tr[ls] + lazy[rt] * (mid - l + 1) % p) % p;        tr[rs] = (tr[rs] + lazy[rt] * (r - mid) % p) % p;        lazy[rt] = 0;    }}void build(int rt, int l, int r){
       if(l == r){
           tr[rt] = wt[l];        lazy[rt] = 0;        return;    }    int mid = l + r >> 1;    build(lson);    build(rson);    pushup(rt);}LL query(int rt, int l, int r, int ql, int qr){
       if(ql <= l && r <= qr){
           return tr[rt];    }    pushdown(rt, l, r);    int mid = l + r >> 1;    LL res = 0;    if(ql <= mid) res += query(lson, ql, qr);    if(mid < qr) res += query(rson, ql, qr);    return res % p;}void update(int rt, int l, int r, int ul, int ur, int val){
       if(ul <= l && r <= ur){
           tr[rt] = (tr[rt] + val * (r - l + 1) % p) % p;        lazy[rt] = (lazy[rt] + val) %  p;        return;    }    pushdown(rt, l, r);    int mid = l + r >> 1;    if(ul <= mid) update(lson, ul, ur, val);    if(mid < ur) update(rson, ul, ur, val);    pushup(rt);}//---------------------------------------------------------LL qSon(int x){
    // subtree query    return query(1, 1, n, id[x], id[x] + sz[x] - 1);}LL qRange(int x, int y){
    // path query    LL ans = 0;    while(top[x] != top[y]){
           if(dep[top[x]] < dep[top[y]])swap(x, y);        ans += query(1, 1, n, id[top[x]], id[x]);        ans %= p;        x = fa[top[x]];    }    if(dep[x] < dep[y])swap(x, y);    ans += query(1, 1, n, id[y], id[x]);    return ans %= p;}void uSon(int x, int z){
    // update value in subtree    update(1, 1, n, id[x], id[x] + sz[x] - 1, z);}void uRange(int x, int y, int z){
    // update node value on path    while(top[x] != top[y]){
           if(dep[top[x]] < dep[top[y]])swap(x, y);        update(1, 1, n, id[top[x]], id[x], z);        x = fa[top[x]];    }    if(dep[x] < dep[y])swap(x, y);    update(1, 1, n, id[y], id[x], z);}void dfs(int u, int p){
       sz[u] = 1;    fa[u] = p;    dep[u] = dep[p] + 1;    int msz = 0, node = 0;    for(int v : G[u]){
           if(v == p) continue;        dfs(v, u);        sz[u] += sz[v];        if(sz[v] > msz)msz = sz[v], node = v;    }    son[u] = node;  // heavy son}void dfs2(int u, int topx){
       id[u] = ++dfsid;  // dfs ordering    wt[dfsid] = w[u]; // map origin value to segment tree    top[u] = topx;  // top node on chain    if(son[u])dfs2(son[u], topx);    for(int v : G[u])        if(v != fa[u] && v != son[u])            dfs2(v, v);}int main(){
       IOS;    int root;    cin >> n >> m >> root >> p;    for(int i = 1; i <= n; ++i){
           cin >> w[i];    }    for(int u, v, i = 1; i < n; ++i){
           cin >> u >> v;        G[u].push_back(v);        G[v].push_back(u);    }    dfs(root, 0);//cout << "---" << endl;    dfs2(root, root);//cout << "---" << endl;    build(1, 1, n);    int op, x, y, z;    while(m--){
           cin >> op >> x;        if(op == 1){
               cin >> y >> z;            uRange(x, y, z); // add z on path from x to y        }else if(op == 2){
               cin >> y;            cout << qRange(x, y) << endl; // query value on path from x to y        }else if(op == 3){
               cin >> z;            uSon(x, z); // add z in subtree x        }else{
               cout << qSon(x) << endl; // query subtree x        }    }}

题意：n个点的有根树上，有m个girl，第 $i$ 个girl的初始重量为 $i$ 。有两种操作。

在(u,v)路径上，找最轻的k个girl，并删除。

把v子树上所有的女孩的体重增加k。

思路：树链剖分模板题。搞一个vector数组girl[v]表示v点上的女孩列表。reverse之后，列表中的女孩数量单调递减。

找 $k$ 个最轻的女孩相当于分 $k$ 次找，只要考虑找最大即可。

线段树维护<该段最轻体重，其所在的点>。

找出之后，要把女孩pop掉，并重置线段树该点为下一个女孩的原始重量加曾经加过的重量。加过的重量可以通过刚刚pop掉的女孩的原始重量算出。

#include
   
    using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define endl '\n'#define fi first#define se second#define mp make_pair#define lson rt << 1, l, mid#define rson rt << 1|1, mid + 1, r#define dj cout << "hello" << endl;typedef long long LL;typedef pair
    
      PLI;const int N = 1e5 + 5;const LL INF = 2e18;int n, m, q;vector
     
       G[N], girl[N];int dfsid = 0;int top[N], son[N], sz[N], dep[N], id[N], fa[N];int wt[N];LL lazy[N << 2];PLI tr[N << 2];//----------------  segment tree  --------------------------void pushup(int rt){
       tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]);}void pushdown(int rt, int l, int r){
       if(lazy[rt]){
           int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1;        lazy[ls] = lazy[ls] + lazy[rt];        lazy[rs] = lazy[rs] + lazy[rt];        tr[ls].first = tr[ls].first + lazy[rt];        tr[rs].first = tr[rs].first + lazy[rt];        lazy[rt] = 0;    }}LL getGirl(int x, LL dv = 0){
       if(girl[x].empty())return INF;    else return girl[x].back() + dv;}void build(int rt, int l, int r){
       if(l == r){
           tr[rt] = make_pair(getGirl(wt[l]), wt[l]);        lazy[rt] = 0;        return;    }    int mid = l + r >> 1;    build(lson);    build(rson);    pushup(rt);}PLI query(int rt, int l, int r, int ql, int qr){
       //cout << rt << "===" << l << " " << r << endl;    if(ql <= l && r <= qr){
           return tr[rt];    }    pushdown(rt, l, r);    int mid = l + r >> 1;    PLI res(INF, -1);    if(ql <= mid) res = min(res, query(lson, ql, qr));    if(mid < qr) res = min(res, query(rson, ql, qr));    return res;}void update(int rt, int l, int r, int ul, int ur, int val){
       if(ul <= l && r <= ur){
           tr[rt].first = tr[rt].first + val;        lazy[rt] = lazy[rt] + val;        return;    }    pushdown(rt, l, r);    int mid = l + r >> 1;    if(ul <= mid) update(lson, ul, ur, val);    if(mid < ur) update(rson, ul, ur, val);    pushup(rt);}void set_element(int rt, int l, int r, int key, LL dv){
       if(id[key] == r && id[key] == l){
           tr[rt] = make_pair(getGirl(key, dv), key);        lazy[rt] = 0;        return;    }    pushdown(rt, l, r);    int mid = l + r >> 1;    if(id[key] <= mid) set_element(lson, key, dv);    else set_element(rson, key, dv);    pushup(rt);}//---------------------------------------------------------PLI qRange(int x, int y){
    // path query    PLI ans(INF, -1);    while(top[x] != top[y]){
           if(dep[top[x]] < dep[top[y]])swap(x, y);        ans = min(ans, query(1, 1, n, id[top[x]], id[x]));        x = fa[top[x]];    }    if(dep[x] < dep[y])swap(x, y);    ans = min(ans, query(1, 1, n, id[y], id[x]));    return ans;}void uSon(int x, int z){
    // update value in subtree    update(1, 1, n, id[x], id[x] + sz[x] - 1, z);}void dfs(int u, int p){
       sz[u] = 1;    fa[u] = p;    dep[u] = dep[p] + 1;    int msz = 0, node = 0;    for(int v : G[u]){
           if(v == p) continue;        dfs(v, u);        sz[u] += sz[v];        if(sz[v] > msz)msz = sz[v], node = v;    }    son[u] = node;  // heavy son}void dfs2(int u, int topx){
       id[u] = ++dfsid;  // dfs ordering    wt[dfsid] = u; // map origin value to segment tree    top[u] = topx;  // top node on chain    if(son[u])dfs2(son[u], topx);    for(int v : G[u])        if(v != fa[u] && v != son[u])            dfs2(v, v);}int main(){
       IOS;    cin >> n >> m >> q;    for(int v, u, i = 1; i < n; ++i){
           cin >> v >> u;        G[v].push_back(u);        G[u].push_back(v);    }    for(int ci, i = 1; i <= m; ++i){
           cin >> ci;        girl[ci].push_back(i);    }    for(int i = 1; i <= n; ++i)        reverse(girl[i].begin(), girl[i].end());    dfs(1, 0);    dfs2(1, 1);    build(1, 1, n);    while(q--){
           int op, v, u, k;        cin >> op >> v;        if(op == 1){
               cin >> u >> k;            vector
      
        ans;            PLI tmp;            while(k--){
                   if((tmp = qRange(v, u)).first == INF)break;                ans.push_back(girl[tmp.second].back());                LL dv = tmp.first - girl[tmp.second].back();                girl[tmp.second].pop_back();                set_element(1, 1, n, tmp.second, dv);            }            cout << ans.size();            for(LL i : ans)                cout << " " << i;            cout << endl;        }else{
               cin >> k;            uSon(v, k);        }    }}

倍增思路

题意：一棵有点权的树上，每次查询u和v之间路径上最大异或和。多次查询。

思路： 对于每个f[x][i]求出整段的线性基。那么查询只需要在倍增求lca过程中合并线性基就行了。

#include 
   
    #define endl '\n'using namespace std;using ll = long long;const int maxn = 2e4 + 5;struct JI{
       ll a[62];    JI(){
           memset(a, 0, sizeof(a));    }    void add(ll x){
           for(ll i = 60; i >= 0; --i){
               if(x & (1ll<
    
     = 0; --i)            base = max(base, base ^ a[i]);        return base;    }};vector
     
       G[maxn];int dep[maxn], f[maxn][20];ll a[maxn];JI ji[maxn][20];JI merge_ji(const JI &x, const JI &y){
       JI res;    for(int i = 60; i >= 0; --i){
           if(x.a[i])res.add(x.a[i]);        if(y.a[i])res.add(y.a[i]);    }    return res;}void dfs(int u, int fa, int d){
       f[u][0] = fa;    ji[u][0].add(a[u]);    dep[u] = d;    for(int son : G[u]){
           if(son==fa)continue;        dfs(son, u, d + 1);    }}JI lca(int x, int y){
       if(dep[x] < dep[y])swap(x, y);    int t = dep[x] - dep[y];    JI res;    for(int i=0;i<20;++i)        if(t&(1<
      
       =0;--i){
           if(f[x][i] != f[y][i]){
               res = merge_ji(res, ji[x][i]);            res = merge_ji(res, ji[y][i]);            x = f[x][i];            y = f[y][i];        }    }    res.add(a[x]);    res.add(a[y]);    res.add(a[f[x][0]]);    return res;}int main() {
       ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int n, q;    cin >> n >> q;    for(int i = 1; i <= n; ++i){
           cin >> a[i];    }    int x, y;    for(int i=1;i
       
        > x >> y;        G[x].push_back(y);        G[y].push_back(x);    }    dfs(1, 0, 1);    for(int i = 1; i < 20; ++i){
           for(int j = 1; j <= n; ++j){
               f[j][i] = f[f[j][i-1]][i-1];            ji[j][i] = merge_ji(ji[j][i-1], ji[f[j][i-1]][i-1]);        }    }    while(q--){
           cin >> x >> y;        cout << lca(x, y).jmax(0) << endl;    }}

并查集

题意：给一棵有边权树，求有序三元组 $(i, j, k)$ ， $i$ 到 $j$ ， $i$ 到 $k$ 的路径上都有Lucy边。（Lucy边：边权每一位都是4或7）

思路：

只要求到每个点 $i$ 经过Lucy边能到达的点数 $s_i$ ，则答案就是 $\sum_{1\le i \le n}s_i\cdot (s_i - 1)$ 。

任意两个点的路径上没有Lucy边的话， $s_i==s_j$ 。

所以，可以并查集把没有Lucy边相连的点合在一起，则 $s_i=n-siz[i]$

#include
   
    using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//#define endl '\n'typedef long long LL;const int N = 1e5 + 5;int n, f[N], siz[N];bool is47(int x){
       while(x){
           if(x % 10 != 7 && x % 10 != 4)return false;        x /= 10;    }    return true;}int findroot(int x){
       return f[x] == x ? x : (f[x] = findroot(f[x]));}bool merge(int x, int y){
       x = findroot(x), y = findroot(y);    if(x != y){
           f[x] = y;        siz[y] += siz[x];        siz[x] = 0;        return true;    }    return false;}int main(){
       IOS;    cin >> n;    for(int i = 1; i <= n; ++i){
           f[i] = i;        siz[i] = 1;    }    for(int u, v, w, i = 1; i < n; ++i){
           cin >> u >> v >> w;        if(!is47(w))merge(u, v);    }    LL ans = 0;    for(int i = 1; i <= n; ++i){
           if(f[i] != i)continue;        ans += 1ll * siz[i] * (n - siz[i]) * (n - siz[i] - 1);    }    cout << ans << endl;}

转载地址：http://wwuzi.baihongyu.com/

你可能感兴趣的文章