题3 - 树上路径 题目支持3种操作 1.将以u为根的子树内节点(包括u)的权值加val 2.将(u, v)路径上的节点权值加val 3.询问(u, v)路径上节点的权值两两相乘的和 思路：很明显，唯一有难度的就是操作3。 我们换位思考，要计算一个数组内元素两两相乘之和，其实就等于（元素之和的平方-元素平方之和）/2，即对于数组a，求 [(∑i=1nai)2−∑i=1nai2]/2 [(\sum_{i=1}^n a_i)^2-\sum_{i=1}^n a_i^2]/2[(∑i=1n​ai​)2−∑i=1n​ai2​]/2。 因此我们不仅要维护区间和，还要维护区间内元素平方之和，特别推导一下修改...

题2 - [HAOI2015]树上操作 题目支持3种操作： 操作 1 ：把某个节点 x 的点权增加 a 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和 思路：树链剖分模板题。（a可以是负数，我线段树的板子一直都是tag>0才去push_down，找了半天bug(((φ(◎ロ◎;)φ)))） 代码： #include<bits/stdc++.h> #define ll long long #define L(i,j,k) for(ll i=(j);i<=(k);i++) #define R(i,j,...

题1 - [LNOI2014]LCA 题目支持q个询问[l,r]中的结点与z结点的lca的深度之和，即∑l≤i≤rdeep[LCA(i,z)] \sum_{l≤i≤r} deep[LCA(i,z)]∑l≤i≤r​deep[LCA(i,z)] 思路：很明显，在1≤n≤50000,1≤m≤50000的条件下，在线查询lca的复杂度直接爆炸，因此我们考虑离线（嗯，想到这一步后就gg了） 既然直接查询lca不行，那么我们换一种想法。仔细想想，我们要查的其实并不是lca，而是lca的深度。 我们把 i 到根节点的这条链上权值+1，然后再询问 z 到根节点的链上权值之和，我们会发现，其实这就等于lca的深...

浅谈 - 树链剖分 前言：其实只是最近练了一些题后，总结一下下 树链剖分，其实就是把一棵树拆成多条树链，而两点之间所访问的树链是logn量级，因此给了我们很大的操作空间 而一棵树，根据dfn映射到数组上，一条树链就是数组上一段区间。因此我们可以用前缀和、线段树、树状数组等等进行区间操作，区间操作的复杂度也为Ologn（前缀和为O1） 最近练的一些题：（感谢zngg的题） 题1 - [LNOI2014]LCA 链接：https://ac.nowcoder.com/acm/contest/22131/A 题目支持q个询问[l,r]中的结点与z结点的lca的深度之和，即∑l≤i≤rdeep[LC...

树链剖分 前言：树链剖分，久闻大名。从半年前了解到这个知识点，却一直拖到寒假才来学...emm，确实拖了挺久的。 小小总结一下，每个父节点都有一个重儿子和若干轻儿子，从一个轻结点出发，一直沿着重儿子延伸下去，就是一条重链。 因此，一颗树就被剖分成了若干重链与若干叶子结点。并且，每一条重链的头都是轻结点（根也是轻结点）。 我的一些心得是，可以把一条重链看作是一个并查集，并查集的头是轻结点，同时若干并查集之间相互关联。 具体的一些实现过程： 跑一遍dfs1，标记以下内容： 结点的父亲fa 结点的深度dep 结点的大小siz 结点的重儿子son（取决于结点的大小） 再跑一遍dfs2，标记以...

2021ICPC上海站-补题 前言：打铁的第二站，思维太过僵硬，专业知识还不够深。赛中过了DEG，然后I题dp没想出来，罚坐4小时… 比赛链接：https://ac.nowcoder.com/acm/contest/24872 E题（签到·贪心） 题意： 从n个数中选m个，使其两两之间差值≥k 思路： 贪心的想，先排序，从头开始取，保证现在取的数比上一次取的要大于等于k #include<bits/stdc++.h> #define ll long long using namespace std; const ll inf=1e18; ll n,m,k,ans; ll a[20...

Emm... 照着标答写的码，再详细捋一遍 题目大意： 给了一个以 1 为根的有根树，儿子的权值小于父亲的权值。 多次询问，病毒在 节点爆发，可以向任何权值范围在 的节点传播，求最多扩散了多少个节点。 整体思路： 1、先让病毒向上传播到 节点，满足 节点的父节点权值。（这样可以确保病毒只会在以 为根的子树上传播）2、然后求以为根的子树上，有多少节点权值 操作过程： （在线做法）0、前向星存图，权值离散化 void add(ll u,ll v,ll w){ eg[++cnt].to=v; eg[cnt].nxt=head[u]; eg[cnt].w=w; he...

C题dp大法好没考虑太多 存储 代表第 人 代表第 个棋子 开了 （1-N）表示在前 个棋子里面选 （0-15）表示四位二进制数，比如“1101”代表一、二、四号选了棋子，三号还没选棋子 至此我们可以推出 比如当 总结下规律，简化代码，可以得到 dp[i][j]=dp[i-1][j]; ll t=0,m=j; while(m>0){ if(m%2==1){ ll p=pow(2,t); dp[i][j]+=dp[i-1][j-p]*a[4-t][i]; } t...