洛谷 5314 「Ynoi 2011」ODT

以前没卡过去，今天突发奇想重新交了一下就过了（
O(nlog2n) 过百万实锤（

不难想到链分治，对每个点开一棵平衡树维护轻儿子，不难发现轻儿子的个数和应当是 O(nlogn) 级别的。
修改可以直接暴力树剖 O(log2n) 草，查询是大常数 O(logn)。

建议用 Treap。

代码：

#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1e6;
int n,m,a[N + 5];
vector<int> e[N + 5];
namespace BIT
{
    int c[N + 5];
    #define lowbit(x) ((x) & -(x))
    inline void update(int x,int k)
    {
        for(;x <= n;x += lowbit(x))
            c[x] += k;
    }
    inline int query(int x)
    {
        int ret = 0;
        for(;x;x -= lowbit(x))
            ret += c[x];
        return ret;
    }
};
namespace Treap
{
    int val[N + 5],cnt[N + 5],rnd[N + 5],sz[N + 5],ch[N + 5][2];
    int rt[N + 5],st[N + 5],top;
    inline void push(int p)
    {
        sz[p] = sz[ch[p][0]] + cnt[p] + sz[ch[p][1]];
    }
    inline void rotate(int &p,int d)
    {
        int q = ch[p][d ^ 1];
        ch[p][d ^ 1] = ch[q][d],ch[q][d] = p;
        push(p),push(p = q);
    }
    inline int new_node(int v)
    {
        static int tot = 0;
        int p = top ? st[top--] : ++tot;
        val[p] = v,cnt[p] = sz[p] = 1,rnd[p] = rand(),ch[p][0] = ch[p][1] = 0;
        return p;
    }
    void insert(int &p,int v)
    {
        if(!p)
        {
            p = new_node(v);
            return ;
        }
        ++sz[p];
        if(val[p] == v)
        {
            ++cnt[p];
            return ;
        }
        int d = v > val[p];
        insert(ch[p][d],v),rnd[p] < rnd[ch[p][d]] && (rotate(p,d ^ 1),1),push(p);
    }
    void remove(int &p,int v)
    {
        if(!p)
            return ;
        if(v < val[p])
            remove(ch[p][0],v);
        else if(v > val[p])
            remove(ch[p][1],v);
        else if(!ch[p][0] && !ch[p][1])
            !(--cnt[p],--sz[p]) && (st[++top] = p,p = 0);
        else if(ch[p][0] && !ch[p][1])
            rotate(p,1),remove(ch[p][1],v);
        else if(!ch[p][0] && ch[p][1])
            rotate(p,0),remove(ch[p][0],v);
        else
        {
            int d = rnd[ch[p][0]] > rnd[ch[p][1]];
            rotate(p,d),remove(ch[p][d],v);
        }
        push(p);
    }
    int kth(int p,int k)
    {
        if(!p)
            return 0;
        if(k <= sz[ch[p][0]])
            return kth(ch[p][0],k);
        else if(k > cnt[p] + sz[ch[p][0]])
            return kth(ch[p][1],k - cnt[p] - sz[ch[p][0]]);
        return val[p];
    }
};
namespace HLD
{
    int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5];
    void dfs1(int p)
    {
        sz[p] = 1;
        for(register vector<int>::iterator v = e[p].begin();v != e[p].end();++v)
            if(*v ^ fa[p])
            {
                fa[*v] = p,dep[*v] = dep[p] + 1,dfs1(*v),sz[p] += sz[*v];
                if(!son[p] || sz[son[p]] < sz[*v])
                    son[p] = *v;
            }
    }
    void dfs2(int p)
    {
        static int tot = 0;
        id[p] = ++tot;
        if(son[p])
            top[son[p]] = top[p],dfs2(son[p]);
        for(register vector<int>::iterator v = e[p].begin();v != e[p].end();++v)
            if(!id[*v])
                Treap::insert(Treap::rt[p],a[*v]),top[*v] = *v,dfs2(*v);
    }
    void update(int x,int y,int k)
    {
        while(top[x] ^ top[y])
            if(dep[top[x]] > dep[top[y]])
            {
                Treap::remove(Treap::rt[fa[top[x]]],a[top[x]]);
                BIT::update(id[top[x]],k),BIT::update(id[x] + 1,-k),a[top[x]] += k;
                Treap::insert(Treap::rt[fa[top[x]]],a[top[x]]);
                x = fa[top[x]];
            }
            else
            {
                Treap::remove(Treap::rt[fa[top[y]]],a[top[y]]);
                BIT::update(id[top[y]],k),BIT::update(id[y] + 1,-k),a[top[y]] += k;
                Treap::insert(Treap::rt[fa[top[y]]],a[top[y]]);
                y = fa[top[y]];
            }
        if(dep[x] > dep[y])
            swap(x,y);
        if(top[x] == x && (x ^ 1))
            Treap::remove(Treap::rt[fa[x]],a[x]),a[x] += k,Treap::insert(Treap::rt[fa[x]],a[x]);
        BIT::update(id[x],k),BIT::update(id[y] + 1,-k);
    }
    int query(int x,int k)
    {
        static int buf[10];
        int tot = 0;
        k <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k));
        k > 1 && k - 1 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 1));
        k > 2 && k - 2 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 2));
        k > 3 && k - 3 <= Treap::sz[Treap::rt[x]] && (buf[++tot] = Treap::kth(Treap::rt[x],k - 3));
        buf[++tot] = BIT::query(id[x]);
        fa[x] && (buf[++tot] = BIT::query(id[fa[x]]));
        son[x] && (buf[++tot] = BIT::query(id[son[x]]));
        sort(buf + 1,buf + tot + 1);
        return buf[min(k,4)];
    }
};
int main()
{
    srand(20070921),read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    int u,v;
    for(register int i = 1;i < n;++i)
        read(u),read(v),e[u].push_back(v),e[v].push_back(u);
    HLD::dep[1] = HLD::top[1] = 1,HLD::dfs1(1),HLD::dfs2(1);
    for(register int i = 1;i <= n;++i)
        BIT::update(HLD::id[i],a[i]),BIT::update(HLD::id[i] + 1,-a[i]);
    for(int op,x,y,z;m;--m)
    {
        read(op),read(x),read(y);
        if(op == 1)
            read(z),HLD::update(x,y,z);
        else
            printf("%d\n",HLD::query(x,y));
    }
}