bzoj3052 [wc2013]糖果公园

3052: [wc2013]糖果公园

Time Limit: 200 Sec Memory Limit: 512 MB
Submit: 1438 Solved: 749
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

84
131
27
84

HINT

分析：没想到这能用莫队来做......

　　　先看数据，10w,应该是nlogn的算法？时限有200s,nsqrt(n)应该也可以. 于是开始想根号算法.

　　　树上的根号算法？先把问题化简一下：如果没有修改操作并且是在序列上操作.

　　　化简后的题目就非常好做了，莫队裸题.维护一个桶即可.

　　　有修改操作该怎么办呢？带修改的莫队就好了嘛，详情可见：bzoj2120.

　　　在树上怎么办呢？树上的带修改的莫队？这是个什么东西......实际上确实有这种算法.

　　　首先要像普通莫队算法一样给树分块,至于怎么给树分块？可见：bzoj1086.

　　　然后就和普通莫队算法差不多啦，维护两个指针L和R，一个数组vis表示i这个点有没有被计入答案中. 如果(L,R) 转移到 (L',R')，第一想法肯定是将路径(L,L')和路径(R,R')上的点的vis全部取反，然后更新答案. 这样会有一个问题：如果一开始L,R在L',R'的LCA处，那么这样LCA会被取反两次，没有被统计进入答案. 这是因为两条路径在LCA处可能会重叠！

　　　怎么办呢？先不考虑LCA就好了. (L,R)转移到(L',R'),将路径(L,L')和路径(R,R')上的点除了L和L'的LCA 以及 R和R'的LCA都取反. 在草稿纸上画几个例子就能发现，这个方法统计的答案一定不会包含当前（L,R）的LCA,但是包含路径上其它的所有点. 最后单独算一下LCA的贡献就好了.

　　　注意点：先单独处理第一个询问以及在它之前的修改. 这一步是直接从(L,L)转移到(R,R). 在dfs时要维护dfs序，如果查询的l的dfs序＞r的dfs序，则交换l,r.

　　　总结一下树上带修改的莫队吧:

　　　1.先对树进行分块.

　　　2.对查询数组进行排序.

　　　3.单独处理第一个询问以及之前的修改.

　　　4.先移动Time指针，再直接从(L,R)转移到(L',R'),分别对应上一次询问的l,r和这一次询问的l,r.

　　　如何修改？

　　　单点修改：如果vis[x] == 0,否则先把消掉x原本的颜色，再换颜色，统计贡献.

　　　路径修改：每次把深度大的往上跳，单点修改.直到两个点重合.

　　　每次修改完路径后要修改LCA,统计答案后还原LCA.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200010;
int n,m,Q,head[maxn],to[maxn],nextt[maxn],tot = 1,w[maxn],v[maxn],fa[maxn][20];
int deep[maxn],belong[maxn],ecnt = 0,c[maxn],block,top,sta[maxn],last[maxn];
int cnt1,cnt2,col[maxn],tong[maxn],vis[maxn],pos[maxn],dfs_clock;
long long ans,anss[maxn];

struct node1
{
    int l,r,id,tim,lpos,rpos;
} q[maxn];

struct node2
{
    int x,y,last;
} md[maxn];

void add(int x,int y)
{
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

int dfs(int u,int faa)
{
    pos[u] = ++dfs_clock;
    int left = 0;
    fa[u][0] = faa;
    deep[u] = deep[faa] + 1;
    for (int i = head[u]; i; i = nextt[i])
    {
        int v = to[i];
        if (v == faa)
            continue;
        left += dfs(v,u);
        if (left >= block)
        {
            ++ecnt;
            while (left)
            {
                belong[sta[top--]] = ecnt;
                left--;
            }
        }
    }
    sta[++top] = u;
    return left + 1;
}

bool cmp(node1 a,node1 b)
{
    if (a.lpos == b.lpos && a.rpos == b.rpos)
        return a.tim < b.tim;
    if (a.lpos == b.lpos)
        return a.rpos < b.rpos;
    return a.lpos < b.lpos;
}

int lca(int x,int y)
{
    if (deep[x] < deep[y])
        swap(x,y);
    for (int i = 19; i >= 0; i--)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}

void update3(int x)
{
    if (vis[x])
    {
        vis[x] = 0;
        ans -= 1LL * w[tong[col[x]]] * v[col[x]];
        tong[col[x]]--;
    }
    else
    {
        vis[x] = 1;
        tong[col[x]]++;
        ans += 1LL * w[tong[col[x]]] * v[col[x]];
    }
}

void update1(int x,int v)
{
    if (!vis[x])
        col[x] = v;
    else
    {
        update3(x);
        col[x] = v;
        update3(x);
    }
}

void update2(int x,int y)
{
    while (x != y)
    {
        if (deep[x] < deep[y])
        {
            update3(y);
            y = fa[y][0];
        }
        else
        {
            update3(x);
            x = fa[x][0];
        }
    }
}

void solve()
{
    int Time = q[1].tim;
    for (int i = 1; i <= Time; i++)
        update1(md[i].x,md[i].y);
    update2(q[1].l,q[1].r);
    int LCA = lca(q[1].l,q[1].r);
    update3(LCA);
    anss[q[1].id] = ans;
    update3(LCA);
    for (int i = 2; i <= cnt2; i++)
    {
        while (Time < q[i].tim)
        {
            ++Time;
            update1(md[Time].x,md[Time].y);
        }
        while (Time > q[i].tim)
        {
            update1(md[Time].x,md[Time].last);
            Time--;
        }
        update2(q[i - 1].l,q[i].l);
        update2(q[i - 1].r,q[i].r);
        LCA = lca(q[i].l,q[i].r);
        update3(LCA);
        anss[q[i].id] = ans;
        update3(LCA);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    block = pow(n,2.0 / 3.0);
    for (int i = 1; i <= m; i++)
        scanf("%d",&v[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d",&w[i]);
    for (int i = 1; i < n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
　　 ++ecnt;
    while (top)
        belong[sta[top--]] = ecnt;
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&col[i]);
        last[i] = col[i];
    }
    for (int i = 1; i <= Q; i++)
    {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if (opt == 0)
        {
            ++cnt1;
            md[cnt1].x = x;
            md[cnt1].y = y;
            md[cnt1].last = last[x];
            last[md[cnt1].x] = md[cnt1].y;
        }
        else
        {
            if (pos[x] > pos[y])
                swap(x,y);
            ++cnt2;
            q[cnt2].tim = cnt1;
            q[cnt2].id = cnt2;
            q[cnt2].l = x;
            q[cnt2].r = y;
            q[cnt2].lpos = belong[x];
            q[cnt2].rpos = belong[y];
        }
    }
    sort(q + 1,q + 1 + cnt2,cmp);
    solve();
    for (int i = 1; i <= cnt2; i++)
        printf("%lld
",anss[i]);

    return 0;
}