HDU 5405 Sometimes Naive 2015多校聯合訓練賽#9 LCT 樹鍊剖分

Sometimes Naive

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 11    Accepted Submission(s): 6

Problem Description Rhason Cheung had a naive problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help.

She has a tree with  n  vertices, numbered from  1  to  n . The weight of  i -th node is  wi .

You need to support two kinds of operations: modification and query.

For a modification operation  u,w , you need to change the weight of  u -th node into  w .

For a query operation  u,v , you should output  ∑ni=1∑nj=1f(i,j) . If there is a vertex on the path from  u  to  v  and the path from  i  to  j  in the tree,  f(i,j)=wiwj , otherwise  f(i,j)=0 . The number can be large, so print the number modulo  109+7

Input There are multiple test cases.

For each test case, the first line contains two numbers  n,m(1≤n,m≤105) .

There are  n  numbers in the next line, the  i -th means  wi(0≤wi≤109) .

Next  n−1  lines contain two numbers each,  ui  and  vi , that means that there is an edge between  ui  and  vi .

The following are  m  lines. Each line indicates an operation, and the format is " 1 u w "(modification) or " 2 u v "(query) (0≤w≤109)  

Output For each test case, print the answer for each query operation.

Sample Input

6 5
1 2 3 4 5 6
1 2
1 3
2 4
2 5
4 6
2 3 5
1 5 6
2 2 3
1 1 7
2 2 4
        

Sample Output

341
348
612
        

Author xudyh  

Source 2015 Multi-University Training Contest 9

根據題意求所有i,j路徑經過路徑u,v上的點，那麼對wi*wj累加

反面考慮：所有路徑累加和 - 不經過路徑的累加和

那麼隻需快速得到不在路徑上子樹的規模，他們的平方的累加和就是結果。

解題報告用的是樹鍊剖分。我還沒想好怎麼實作。

比賽的時候想到LCT了，但是之前沒寫過用子樹标記父親的标記的代碼，是以最後也沒打出來。

但是之前看過别人有實作過，晚上想一想也想到了。

如何實作LCT的結點記錄自己子樹的資訊：

        用一個标記如S1，記錄，這個标記隻有在斷開連接配接或者建立連接配接的時候才會更新。然後用一個S2，這個标記是用于splay上做更新的

于是s1的更改隻需在access操作更改，而s2隻需update時更新即可。

如果要用我的代碼當模闆注意我的注釋哦。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 200007
#define inf  1000000000
#define ll long long
ll mod = 1000000007;
struct Node{
    Node *fa,*ch[2];
    bool rev,root;//基本結構不需要修改
    ll val,s1,s2,s3,s4;//這裡的标記可以更改
};
Node pool[maxn];
Node *nil,*tree[maxn];
int cnt = 0;
void init(){
    cnt = 1;
    nil = tree[0] = pool;
    nil->ch[0] = nil->ch[1] = nil;
    nil->s1 = nil->s2 = nil->val = nil->s3 = nil->s4 = 0;
}
Node *newnode(ll val,Node *f){ 
    pool[cnt].fa = f;
    pool[cnt].ch[0]=pool[cnt].ch[1]=nil;
    pool[cnt].rev = false;
    pool[cnt].root = true;//以下可修改
    pool[cnt].val = val;
    pool[cnt].s1 = 0;
    pool[cnt].s2 = 0;
    pool[cnt].s3 = 0;
    pool[cnt].s4 = 0;
    return &pool[cnt++];
}

//左右子樹反轉******真正把結點變為根
void update_rev(Node *x){
    if(x == nil) return ;
    x->rev = !x->rev;
    swap(x->ch[0],x->ch[1]);
}
//splay向上更新資訊******
void update(Node *x){//splay需要自己寫更新代碼
    if(x == nil) return ;
    x->s2 = x->s1 + x->val;
    x->s4 = x->s3;
    if(x->ch[0] != nil){
        x->s2 += x->ch[0]->s2;
        if(x->s2 >= mod)
            x->s2 -= mod;
        x->s4 += x->ch[0]->s4;
        x->s4 %= mod;
    }
    if(x->ch[1] != nil){
        x->s2 += x->ch[1]->s2;
        if(x->s2 >= mod)
            x->s2 -= mod;
        x->s4 += x->ch[1]->s4;
        x->s4 %= mod;
    }
}

//splay下推資訊******
void pushdown(Node *x){//樹的反轉，才能保證把一個結點提為根。如果有其他下推操作，自己加入
    if(x->rev != false){
        update_rev(x->ch[0]);
        update_rev(x->ch[1]);
        x->rev = false;
    }
}
//splay在root-->x的路徑下推資訊******
void push(Node *x){//不需要改
    if(!x->root) push(x->fa);
    pushdown(x);
}
//将結點x旋轉至splay中父親的位置******
void rotate(Node *x){//旋轉操作，不太需要改，除非有懶标記，需要加上pushdown，update
    Node *f = x->fa, *ff = f->fa;
    int t = (f->ch[1] == x);
    if(f->root)
        x->root = true, f->root = false;
    else ff->ch[ff->ch[1] == f] = x;
    x->fa = ff;
    f->ch[t] = x->ch[t^1];
    x->ch[t^1]->fa = f;
    x->ch[t^1] = f;
    f->fa = x;
    update(f);
}
//将結點x旋轉至x所在splay的根位置******
void splay(Node *x){//不需要改
    push(x);
    Node *f, *ff;
    while(!x->root){
        f = x->fa,ff = f->fa;
        if(!f->root)
            if((ff->ch[1]==f)&&(f->ch[1] == x)) rotate(f);
            else rotate(x);
        rotate(x);
    }
    update(x);
}
//将x到樹根的路徑并成一條path******
Node *access(Node *x){
    Node *y = nil,*z;
    while(x != nil){
        splay(x);
        z = x->ch[1];//記錄斷開的結點
        x->ch[1]->root = true;
        (x->ch[1] = y)->root = false;
        update(z);

        x->s1 += z->s2;//更新父親資訊
        x->s3 += (z->s2*z->s2);
        x->s1 %= mod;
        x->s3 %= mod;

        x->s1 -= y->s2;
        x->s3 -= y->s2*y->s2;
        x->s1 %= mod;
        x->s3 %= mod;

        update(x);
        y = x;
        x = x->fa;
    }
    return y;
}
//将結點x變成樹根******
void be_root(Node *x){//基本操作
    access(x);
    splay(x);
    update_rev(x);
}

int value[maxn];
vector<int> head[maxn];
void dfs(int u,int f){//dfs建立沒有鍊的森林
    tree[u]->fa = tree[f];
    for(int i = 0;i < head[u].size() ;i++){
        int v = head[u][i];
        if(v == f) continue;
        dfs(v,u);
        tree[u]->s1 += tree[v]->s2;
        tree[u]->s1 %= mod;
        tree[u]->s3 += tree[v]->s2*tree[v]->s2;
        tree[u]->s3 %= mod;
    }
    update(tree[u]);
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i = 1;i <= n; i++)
            scanf("%d",&value[i]);
        for(int i = 0;i <= n; i++)
            head[i].clear();
        int u,v;
        for(int i = 1;i < n; i++){
            scanf("%d%d",&v,&u);
            head[v].push_back(u);
            head[u].push_back(v);
        }
        init();
        for(int i=1;i <= n;i++)
            tree[i] = newnode(value[i],nil);
        dfs(1,0);
        ll total = 0;
        for(int i = 1;i <= n; i++)
            total += value[i];
        total %= mod;

        int t;
        for(int i = 0;i < m; i++){
            scanf("%d%d%d",&t,&u,&v);
            if(t == 1){
                be_root(tree[u]);
                access(tree[u]);
                total = total + v - tree[u]->val;
                total %= mod;
                tree[u]->val = v;
                update(tree[u]);
            }
            else {
                be_root(tree[u]);
                access(tree[v]);
                splay(tree[v]);
                ll ans = total*total%mod-tree[v]->s4;
                ans = (ans%mod+mod)%mod;
                printf("%I64d\n",ans);
            }
        }
    }
    return 0;
}