「BJOI2017」树的难题 TJ+卡题

题目大意

给定一棵 \(n\) 个点的树，每条边有颜色，第 \(i\) 种颜色权值为 \(v_i\)，共 \(m\) 种颜色。
对于树上一条路径，其权值定义为：经过边的颜色依次组成序列，每个相同颜色段的颜色权值之和。
如：颜色序列 \(1,2,2,1,1,4\)，其权值为 \(v_1+v_2+v_1+v_4\)。
给定一对 \(l\)，\(r\)，求出长度在 \([l,r]\) 内的路径的最大权值。
\(1 \le n,m \le 2 \times 10^5,1\le l,r \le n,\mid v_i \mid \le10^4\)。

分析

这道题想清楚了很简单。

首先看到这个路径问题，就往点分治上靠~~，不是点分树，被骗了吧，哈哈哈~~。

重心下单条链是很好算权值的，关键点在于两条链拼接起来，顶端的贡献问题。

想一想可以发现，其实对于每条链，其他的链顶端只有相同和不相同两种。

那就可以一种颜色一种颜色的处理，就可以很方便地维护相同和不相同的颜色。

所以第一步把儿子都提出来，然后按边的颜色排序。

将相同颜色的贡献用 \(now\) 存储，不同的用 \(lst\) 存储。

依次扫描每个儿子，进行如下操作：

遍历其子树，存下每条链的长度和权值。
查询 \(now\) 和 \(lst\) 中答案。
如果和上个儿子的顶端一样，并入 \(now\)；否则将 \(now\) 并入 \(lst\)，然后清空 \(now\) 再并入。

现在就是查询的问题了。

如果这条链长度是 \(len\)，那么另一半长度就要求在 \([l-len,r-len]\) 内。

显然是一个区间查询问题，因为最值不能容斥，硬上线段树。

然后简单做就行了。

实现细节

首先是一个很关键的答案组成问题。

我们查询线段树的时候，如果长度不是从 \(0\) 开始，就需要将一条链组成答案的情况特判。

这个表现在样例一，但测试数据内没有 hack 这个问题……

~~写了三天的 lq 不过样例，一怒之下提交 AC。~~

然后就是线段树区间查询问题，记得跟上下界取 \(\min\) 和 \(\max\)。

线段树涉及到多次清空的问题，动态开点的话可以在新建节点时操作，固定结构的话就用一个 \(lazy-tag\)，访问的时候下传标记即可。

还有两棵权值线段树的合并，这个题里面可以直接用 std::vector 存进行过的操作，然后重新插入一次，毕竟多码多错，少码少错~~，不码不错~~。

Code：

经典的放一半~~，就问你气不气~~：

实在需要拿去对拍啥的也可以找我~~，虽然我也想不出怎么找我~~。

    SegmentTree lst,now;//lst 和 now 的作用见上
    std::vector<std::pair<int,long long>> vec;
    std::vector<std::pair<int,long long>> pos;
	//vec 是当前子树，pos 是当前所有同色的子树
    std::vector<edge> son;//存儿子
    void work_calc(int u,int fa,int col,int dep,long long dis){
        vec.emplace_back(dep,dis);//递归计算深度与权值
        for(edge e:G[u])
            if(!vis[e.ver]&&e.ver!=fa)
                work_calc(e.ver,u,e.col,dep+1,dis+(e.col==col?0:val[e.col]));
    }
    void solve(int u){
        vis[u]=1;
        son.clear();
        for(edge e:G[u])
            if(!vis[e.ver])
                son.emplace_back(e);
        std::sort(son.begin(),son.end(),[](edge x,edge y)->bool{
            return x.col<y.col;
        });//排序
        //lambda 表达式，https://oi-wiki.org/lang/lambda/ 有介绍
        int lst_col={-1};//上一个颜色
        lst.init(all);//链的长度不会超过根的 size
        now.init(all);
        pos.clear();
        for(auto e:son){
            if(~lst_col){
                vec.clear();
                work_calc(e.ver,u,e.col,1,val[e.col]);//计算链
                if(e.col==lst_col){//颜色相同
                    for(auto it:vec)
                        ans=std::max({ans,l<=it.first&&it.first<=r?it.second:-Inf,lst.query(l-it.first,r-it.first)+it.second,now.query(l-it.first,r-it.first)+it.second-val[e.col]});//查询
                    for(auto it:vec)
                        now.updata(it.first,it.second),pos.emplace_back(it.first,it.second);//更新
                }
                else{//新颜色
                    for(auto it:pos)
                        lst.updata(it.first,it.second);//此时之前的 now 等效于 lst
                    pos.clear();
                    now.init(all);
                    for(auto it:vec)
                        ans=std::max({ans,l<=it.first&&it.first<=r?it.second:-Inf,lst.query(l-it.first,r-it.first)+it.second});
                    for(auto it:vec)//清空后的新数据
                        now.updata(it.first,it.second),pos.emplace_back(it);
                }
                lst_col=e.col;
            }
            else{//特殊处理第一棵
                vec.clear();
                work_calc(e.ver,u,e.col,1,val[e.col]);
                for(auto it:vec)
                    ans=std::max(ans,l<=it.first&&it.first<=r?it.second:-Inf);
                for(auto it:vec)
                    now.updata(it.first,it.second),pos.emplace_back(it);
                lst_col=e.col;
            }
        }
        //...递归继续处理
    }