题解 CF490F Treeland Tour

· · 个人记录

又 TM 正解附近徘徊……

一拿到这道题就基本确定是启发式合并，因为这个确实太像求树的重心那种感觉，找两条子树的链然后还要用这层状态更新父亲层状态……

我们对每个点暴力维护一个向下最长的递增长度和最长递减长度，接着我们直接在枚举子树时枚举完一棵就把信息往大树里面塞，塞完后就继续找其他子树然后合并答案，很容易证明我们这么做是不会选到在同一棵子树的情况。整个过程涉及到一个权值的条件然后就是 Max 查找，我们直接上平衡树。很明显的是这个信息的合并平衡树也可以做到，所以我们启发式合并一下，就这？

最开始打了一个很错的东西，想到这个解法后就先码了个 O(n ^ 2) 暴力感觉很稳，接着就开始改改改，好不容易码完了一测过不了样例……

(其实之前还打了个 DSU on tree 但是是错的，至少连 DSU on tree 的正确做法都没有贴到)

有点慌张，接着发现自己的空间还是 O(1e10) 就更慌了，只能给所有点都开个平衡树然后一起合，每个点的平衡树还得封装起来写 vector …… 码到最后还剩 10min 终于可以过样例了，自己造了个链的数据过了然后就觉得很稳接着就交了，很荣幸保龄了。

中午去求叉，被巨佬 @Lucky_Glass 直接爆掉了。

其实这里很好叉，只要我们中间的那个点考虑不选即可……这样我就会少跑很多合法答案，或者说如果最后答案没有中转点连接我就 WA 了……

下午又和巨佬 tr 交流被点醒了：

然后这道题就做完了……怎么说呢？还是特别无语吧……

(代码还是 WA 的，先放到这里改天补，最近多项式的作业太多了……) 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int Len = 1e5 + 5;
int n,m,head[Len],cnt,val[Len],Less[Len],More[Len],MaxLess,MaxMore,ans,dep[Len];
struct Node
{
    int ch[2];
    int ff,val,L,R,LessMax,MoreMax,now;
    Node(){ch[0] = ch[1] = ff = val = L = R = LessMax = MoreMax = now = 0;}
}pks;
struct TS
{
    vector<Node> t;
    int tot;int root;
    void update(int x)
    {
        t[x].MoreMax = t[x].R;
        t[x].LessMax = t[x].L;
        if(t[x].ch[0]) t[x].LessMax = max(t[x].LessMax , t[t[x].ch[0]].LessMax) , t[x].MoreMax = max(t[x].MoreMax , t[t[x].ch[0]].MoreMax);
        if(t[x].ch[1]) t[x].LessMax = max(t[x].LessMax , t[t[x].ch[1]].LessMax) , t[x].MoreMax = max(t[x].MoreMax , t[t[x].ch[1]].MoreMax);
    }
    void rotate(int x)
    {
        int y = t[x].ff , z = t[y].ff , k = t[y].ch[1] == x;
        t[z].ch[t[z].ch[1] == y] = x;
        t[x].ff = z;

        t[y].ch[k] = t[x].ch[k ^ 1];
        t[t[x].ch[k ^ 1]].ff = y;

        t[x].ch[k ^ 1] = y;
        t[y].ff = x;

        update(y) , update(x);
    }
    void Splay(int x,int goal)
    {
        while(t[x].ff != goal)
        {
            int y = t[x].ff , z = t[y].ff;
            if(z != goal) (t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);
            rotate(x);
        }
        if(!goal) root = x;
    }
    void insert(int x,int now)
    {
        int u = root , ff = 0;
        while(u && t[u].ch[x > t[u].val]) ff = u , u = t[u].ch[x > t[u].val];
        u = ++ tot;
        if(ff) t[ff].ch[x > t[ff].val] = u;
        pks.ff = ff , pks.val = x;
        pks.ch[0] = pks.ch[1] = 0;
        pks.L = pks.LessMax = Less[now] , pks.R = pks.MoreMax = More[now];
        pks.now = now;
        t.push_back(pks);
        Splay(u , 0);
    }
    void Find(int x)
    {
        int u = root;
        if(!u) return;
        while(x != t[u].val && t[u].ch[x > t[u].val]) u = t[u].ch[x > t[u].val];
        Splay(u , 0);
    }
    void Next(int x,int f)
    {
        Find(x);
        int u = root;
        //if(val[x] == 2 && f == 1) printf("%d\n",t[u].val);
        if((t[u].val < x && !f) || (t[u].val > x && f)) return;
        //if(val[x] == 2 && f) printf("%d %d\n",t[u].val,t[t[u].ch[1]].val);
        u = t[u].ch[f];
        while(t[u].ch[f ^ 1]) u = t[u].ch[f ^ 1];
        Splay(u , 0); 
    }
    void Print(){for(int i = 2 ; i <= tot ; i ++) printf("%d ",t[i].val);}
}T[Len];
struct node
{
    int next,to;
}edge[Len << 1];
void add(int from,int to)
{
    edge[++ cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
void dfs1(int x,int f)
{
    Less[x] = More[x] = 1;
    for(int e = head[x] ; e ; e = edge[e].next)
    {
        int to = edge[e].to;
        if(to == f) continue;
        dfs1(to , x);
    }
    int nowMaxMore = 0 , nowMaxLess = 0;
    for(int e = head[x] ; e ; e = edge[e].next)
    {
        int to = edge[e].to;
        if(to == f) continue;
        MaxMore = MaxLess = 0;
        T[to].Next(val[x] , 0);
        MaxLess = T[to].t[T[to].t[T[to].root].ch[0]].LessMax;
        if(x == 3) printf("%d\n",MaxLess);
        if(T[to].t[T[to].root].val < val[x]) MaxLess = max(MaxLess , T[to].t[T[to].root].LessMax);

        T[to].Next(val[x] , 1);

        MaxMore = T[to].t[T[to].t[T[to].root].ch[1]].MoreMax;
        if(x == 3) printf("%d\n",MaxMore);
        if(T[to].t[T[to].root].val > val[x]) MaxMore = max(MaxMore , T[to].t[T[to].root].MoreMax);

        //if(x == 2) printf("%d %d\n",MaxLess,MaxMore);
        ans = max(ans , nowMaxMore + MaxLess + 1);
        ans = max(ans , nowMaxLess + MaxMore + 1);
        nowMaxMore = max(nowMaxMore , MaxMore);
        nowMaxLess = max(nowMaxLess , MaxLess);
        //if(T[to].tot > T[x].tot) swap(T[to] , T[x]);
        if(T[to].tot == -1) continue;
        //printf("%d %d\n",to,T[to].tot);
        for(int j = 2 ; j <= T[to].tot ; j ++)
        {
            int Val = T[to].t[j].val , Mores = More[T[to].t[j].now] , Lesss = Less[T[to].t[j].now];
            T[x].insert(T[to].t[j].val , T[to].t[j].now);
        //  printf("%d %d\n",x,T[to].t[j].val);
            T[x].Next(Val , 0);
            ans = max(ans , T[x].t[T[x].t[T[x].root].ch[0]].LessMax + Mores);
            ans = max(ans , Less[T[x].t[T[x].root].now] + Mores);

            T[x].Next(Val , 1);
            ans = max(ans , T[x].t[T[x].t[T[x].root].ch[0]].MoreMax + Lesss);
            ans = max(ans , More[T[x].t[T[x].root].now] + Lesss);
        }
    }
    More[x] = nowMaxMore + 1;
    Less[x] = nowMaxLess + 1;
    //printf("%d %d %d\n",x,Less[x],More[x]);
    T[x].insert(val[x] , x);
    //printf("%d\n",x);T[x].Print();
    //puts(""); 
    //printf("%d %d\n",x,val[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++) 
    {
        scanf("%d",&val[i]);
        T[i].root = 0;T[i].tot = 0;
        T[i].insert(-1e9 , n + 1);
        T[i].insert(1e9 , n + 2);
    }
    pks.val = 0;
    for(int i = 1 ; i < n ; i ++)
    {
        int x,y;scanf("%d %d",&x,&y);
        add(x , y) , add(y , x);
    }
    puts("");
    dfs1(1 , 0);
    //printf("%d\n",ans);
    return 0;
}