题解 P6778 [Ynoi2009] rpdq

FutaRimeWoawaSete · 2021-04-26 14:06:20 · 题解

upd:2021/7/5 太尴尬了，没有发现之前树分块是假的就直接莽上去了，把代码重调了一下，感谢 @b1ngxu 的 Hack 。

相信在二离莫队和top cluster 树分块普及之后，这道题会变得有点尴尬……

首先对于这种 \sum 套 \sum 的维护，我们一般都考虑莫队，毕竟你莫队单点加进去的时候才可以方便拆成一只 \sum 。

在此题的铺垫下，我们考虑这么计算我们的答案：

Ans = \sum_{i = l}^r\sum_{j = i + 1}^r dep(i,j)
Ans = \sum_{i = l} ^ r dep(i) \times (r - l) - \sum_{i = l}^r\sum_{j = i + 1}^r dep(Lca(i,j))

我们发现前面这个东西直接前缀和推一遍就可以维护了，而后面的东西……貌似还是两只 \sum 套一起完全不可做啊。

考虑使用莫队计算答案，如果当前加入的点为 i ，那么我们一次只需要往答案里加上 i 对 [l , r] 的贡献即可。

不过我们发现这样还是不好直接算，套用此题我们知道如果离线下来的话我们可以尝试用前缀的方式进行查询，这让我们想到了二次离线莫队，刚好我们莫队转移时候的贡献也不好计算，所以一次解决俩。

我们以区间右端点平移举例：

区间 [l , r] 平移至区间 [l , r + 1] ，将贡献拆为 [1 , r , r + 1] - [1 , l - 1 , r + 1] ，对于前半还是二离莫队做法单独拿出来算，对于后半，在离线下来推完 [1 , l - 1] 区间的时候拿出来单点查询 1 \sim r + 1 的路径贡献即可。

在这里顺便提一下怎么单点 O(1) 查询1 \sim r + 1 的路径贡献。

维护一段收缩树上的前缀路径贡献，这个每次直接推平即可；
维护树簇内的簇路径贡献；
维护簇路径上内最近一点到这个点路径贡献；

这样的话我们可以直接数组存储这些贡献，就能做到 O(1) 查询了。

还是有点难调，~~当然只要不SB那么也调不了很久~~。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int Len = 2e5 + 5;
int n,m,pos[Len],tem[Len],treebl;
struct node
{
    int to;
    unsigned int val;
    node(){to = val = 0;}
    node(int TO,unsigned int VAL){to = TO , val = VAL;}
}sim;
vector<node> v[Len];
int dep[Len],fa[Len],Fa[Len];
int top[Len],siz[Len],stk[Len],Top,Nearp[Len],cnt,btm[Len],ind[Len],Toper[Len],Btmer[Len];
int ST[Len],Topp;
int block[Len],lenbk;
vector<int> nde[Len];
bool vis[Len];
int val[Len],sum[Len],ADD[Len];
void Add(int from,int to,int val){v[from].push_back(node(to , val));}
void add(int x,int y)
{
    if(y)
    {
        block[++ lenbk] = y;
        Fa[y] = x;
        for(int now = y ; now != x ; now = fa[now]) vis[now] = 1;
    }
    for(int i = 1 ; i <= Top ; i ++) Nearp[stk[i]] = 0;
    for(int i = 1 ; i <= Top ; i ++)
    {
        btm[stk[i]] = y;
        if(stk[i] != y) top[stk[i]] = x;
        if(!y) 
        {
            Nearp[stk[i]] = x;
            continue;
        }
        int p = x;
        for(int now = stk[i] ; now != x ; now = fa[now])
        {
            if(vis[now]) 
            {
                p = now;
                break;
            }
            if(Nearp[now])
            {
                p = Nearp[now];
                break;
            }
        }
        Nearp[stk[i]] = p;
    }
    if(y) for(int now = y ; now != x ; now = fa[now]) vis[now] = 0;
} 
vector<node>::iterator itor;
void dfs(int x,int f)
{ 
    fa[x] = f;
    for (itor = v[x].begin(); itor != v[x].end(); itor ++)
    {
        sim = *itor;
        if (sim.to == f)
        {
            itor = v[x].erase(itor);
            break;
        }
    }
    siz[x] = 1;
    top[x] = 0;
    int Cnt = 0;
    for(int i = 0 ; i < v[x].size() ; i ++)
    {
        int to = v[x][i].to , val = v[x][i].val;
        if(to == f) continue;
        dep[to] = dep[x] + val;
        ST[Topp ++] = to;
        dfs(to , x);
        if(top[to]) Cnt ++ , top[x] = top[to];
        siz[x] += siz[to];
    }
    int Btm = 0;
    if(siz[x] >= treebl || Cnt > 1 || x == 1)
    {
        int sz = 0 , ct = 0;
        for(int i = v[x].size() - 1 ; i >= 0 ; i --)
        {
            int to = v[x][i].to , val = v[x][i].val;
            if(to == f) continue;
            sz += siz[to];
            if(top[to]) ct ++;
            if(sz > treebl || ct > 1)
            {
                sz = siz[to];
                if(top[to]) ct = 1;
                Top = 0;
                cnt ++;
                nde[cnt].clear();
                Btm = 0;
                do
                {
                    stk[++ Top] = ST[-- Topp];
                    Btm = max(Btm , top[ST[Topp]]);
                    ind[ST[Topp]] = cnt;
                    nde[cnt].push_back(ST[Topp]);
                }while(ST[Topp] != v[x][i + 1].to);
                add(x , Btm);
                Toper[cnt] = x , Btmer[cnt] = Btm;
            }
        }
        cnt ++;nde[cnt].clear();Top = 0;Btm = 0;//printf("###%d:\n",cnt);
        do
        {
            stk[++ Top] = ST[-- Topp];
            Btm = max(Btm , top[ST[Topp]]);
            ind[ST[Topp]] = cnt;
            nde[cnt].push_back(ST[Topp]);
        }while(ST[Topp] != v[x][0].to);
        add(x , Btm);
        Toper[cnt] = x , Btmer[cnt] = Btm;
        top[x] = x;
        siz[x] = 1;
    }
}
void Addval(int x)
{
    if(x == 1) return;
    int tmp = (!Fa[x]) ? btm[x] : 0;
    for(int i = 1 ; i < lenbk ; i ++) sum[block[i]] -= sum[Fa[block[i]]];//把收缩树给杀回来，要注意这里1 ~ i其实是深度递减的树簇 
    if(tmp) sum[tmp] += dep[Nearp[x]] - dep[top[x]];
    if(!Fa[x])
    {
        int j = ind[x] , u;
        for(int i = nde[j].size() - 1 ; i >= 0 ; i --) 
        {
            u = nde[j][i];
            if(!Fa[fa[u]]) val[u] -= val[fa[u]];//如果父亲不是top
        }
        for(; !Fa[x] && x > 1 ; x = fa[x]) val[x] += dep[x] - dep[fa[x]];
        for(int i = 0 ; i < nde[j].size() ; i ++)//这里顺序也不能反 
        {
            u = nde[j][i];
            if(!Fa[fa[u]]) val[u] += val[fa[u]];
        }
        //for(int i = 0 ; i < nde[j].size() ; i ++) printf("%d\n",val[nde[j][i]]);
    }
    if(!Fa[x]) x = top[x];
    for(; x >= 1 ; x = Fa[x])
    {
        ADD[x] ++;
        sum[x] += dep[x] - dep[Fa[x]];
    }
    for(int i = lenbk - 1 ; i >= 1 ; i --) sum[block[i]] += sum[Fa[block[i]]];
}
inline unsigned int GetAns(int x)
{
    int bel = ind[x];
    unsigned int res = val[x] * (Btmer[bel] != x) + sum[top[x]];
    if(!Fa[x] && btm[x]) res += (dep[Nearp[x]] - dep[top[x]]) * ADD[btm[x]];
    return res;
}
struct nnode
{
    int l,r;
    unsigned int ans;
    int idx;
}Sec[Len];
struct Node
{
    int l,r,idx,op;
    Node(){l = 0 , r = 0 , idx = 0 , op = 0;}
    Node(const int L , const int R , const int IDX , const int OP){l = L , r = R , idx = IDX , op = OP;}
};
vector<Node> q[Len];
unsigned int Print[Len];
int p1[Len],p2[Len],Block[Len],t,Sum[Len];
bool cmp(nnode x , nnode y)
{
    if(Block[x.l] ^ Block[y.l]) return Block[x.l] < Block[y.l];
    return x.r < y.r;
}
bool cmd(int x,int y){return dep[x] < dep[y];}
signed main()
{
    scanf("%d %d",&n,&m);
    treebl = sqrt(n);
    t = sqrt(n);
    for(int i = 1 ; i <= n ; i ++) Block[i] = (i - 1) / t + 1;
    for(int i = 2 ; i <= n ; i ++) 
    {
        int x,y;unsigned int z;
        scanf("%d %d %u",&x,&y,&z);
        Add(x , y , z) , Add(y , x , z);
    }
    int cnts = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        scanf("%d %d",&Sec[i].l,&Sec[i].r);
        Sec[i].idx = i;
    }
    sort(Sec + 1 , Sec + 1 + m , cmp);
    dfs(1 , 0);
    for(int i = 1 ; i <= cnt ; i ++) sort(nde[i].begin() , nde[i].end() , cmd);
    int l = 1 , r = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        if(l > Sec[i].l) q[r].push_back(Node(Sec[i].l , l - 1 , i , 1)) , l = Sec[i].l;
        if(r < Sec[i].r) q[l - 1].push_back(Node(r + 1 , Sec[i].r , i , -1)) , r = Sec[i].r;
        if(l < Sec[i].l) q[r].push_back((Node){l , Sec[i].l - 1 , i , -1}) , l = Sec[i].l;//因为对于原来的答案而言，现在是要减去这些值，所以把原式取了个-1 
        if(r > Sec[i].r) q[l - 1].push_back((Node){Sec[i].r + 1 , r , i , 1}) , r = Sec[i].r;//与上同 
    }
    Node Calc;
    for(int i = 1 ; i <= n ; i ++)
    {
        p1[i] = GetAns(i);
        Addval(i);
        for(int j = 0 ; j < q[i].size() ; j ++) 
        {
            Calc = q[i][j];
            for(int k = Calc.l ; k <= Calc.r ; k ++) Sec[Calc.idx].ans += Calc.op * GetAns(k);
        }
        p2[i] = GetAns(i);
    }
    l = 1 , r = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        while(l > Sec[i].l) Sec[i].ans -= p2[-- l];
        while(r < Sec[i].r) Sec[i].ans += p1[++ r];
        while(l < Sec[i].l) Sec[i].ans += p2[l ++];
        while(r > Sec[i].r) Sec[i].ans -= p1[r --];
    }
    for(int i = 1 ; i <= n ; i ++) Sum[i] = Sum[i - 1] + dep[i];
    for(int i = 1 ; i <= m ; i ++) Sec[i].ans += Sec[i - 1].ans;
    for(int i = 1 ; i <= m ; i ++) Print[Sec[i].idx] = (Sec[i].r - Sec[i].l) * (Sum[Sec[i].r] - Sum[Sec[i].l - 1]) - 2 * Sec[i].ans;
    for(int i = 1 ; i <= m ; i ++) printf("%u\n",Print[i]);
    return 0;
}