林思艺

分类

日常(1) 题解(41)

/ 注册

全部文章（共42篇）

Propagating tree

题意给你一棵个结点的树, 以为根。每个结点有点权。有次操作：结点权值，的儿子权值，的孙子们，以此类推。询问的点权；思路又是单点查询，看看树状数组吧。区间修改就可以用差分。但是第一个操作有些麻烦，但这和每个节点的深度奇偶有关。所以只需判断一下深度，决定修改的值...

2020-11-10

6 704

求和

题意给你一颗以为根有个节点的树，每个节点有一个点权。给你次操作，操作有两种类型：表示将节点的权值加上；表示求以为根的子树上所有节点的和（包括节点）；分析我们可以通过序将一整棵子树上映射到序列中连续的一段上。所以问题就变成了，单点修改，区间和查询。直...

2020-11-10

4 681

Colorful Tree

题意你有一颗树，每个点有一个颜色，有次操作，将节点改为颜色。询问所有颜色为的点的生成树大小。分析我们可以用序来维护每种颜色的生成树大小。考虑若颜色为的节点只有个、，则其生成树大小就是两个结点在树上的距离，记为。此时，如果加入第个结点，对生成树的贡献能用树上距离算出来：我们分类讨论：...

2020-11-10

3 904

Tree Requests

题意给你一棵有个节点以为根的树，每个节点为的任意字母。有次询问，每次询问给出，指以为根的子树内深度为的所有节点的字母在排列后能否构成一个回文串。分析要排列后成为回文串，所以在符合条件的所有节点之中至多只有一种字母的数量为奇数个，其余的字母数量必定均为偶数个。因为回文...

2020-11-10

4 644

选点

题意你有一棵个节点的二叉树，每个节点有权值，你要选尽量多的点，但是得满足以下限制：对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。分析根的值右子树的最大值左子树的最大值，如果要选择最多的点，那么如...

2020-11-09

8 916

Military Problem

题意你有一棵有个节点的树，有次询问，每次询问有，指从以为根的子树出发到达的第个点是哪一个？如果不存在（即，子树的大小小于），输出。分析很的一道题啊。你先预处理出每个点的序以及每个序对应的点和每棵子树的大小就可以了。询问的时候输出就好了。（数组存的是每个点的序，数组存的是每个序对应的点）. 代码...

2020-11-09

6 677

小A与欧拉路

思路考虑最简单的情况，的情况。每条边就一定是经过两次——去和回。那么遍历完，每条边就需要复制一次，所以。由于不是回路所以可以减去从起点到终点的路径。所以我们要使起点到终点的路径最长。所以问题就是找到树的直径。答案就是。代码 #include<bits/stdc++.h> #defin...

2020-11-03

4 666

棘手的操作

写在前面的确实，题如其名，是一道实实在在的。在隔壁JK_Lover的指导下找到了一篇非常优秀的题解，并悟了一会儿。思路连边和连通性——可以通过并查集维护点的查询和加权——用vector存储每一个连通块的点连通块加权——打标记合并——启发式合并，同时要更新标记全局加——开个变量记录一下（这个操作...

2020-11-02

3 700

Xor-MST

咕了好久终于来写了题意给你个点的无向完全图，每个点有点权，每两个点之间的边权是点权的值。问最小生成树边权和。思路从别人那里学来的巧妙思路，我们考虑树，首先，我们先把样例从高位到低位插入线性基。容易发现，对于每个叶子节点，既每个点值之间，是需要互相连边，那么求他们以后的边的异或值即可。由此可得...

2020-10-29

3 766

Perfect Security

题意给你两个序列，让你求的一种排列，使得得到的序列字典序最小思路贪心的选择与匹配，使得最优。我们将,拆分后 , 贪心就可以方便地进行。枚举两串上,每一位上的数尽量使各位相异或后为即可选择出最合适的。实现还是要用到我们的树来实现。先建立一棵基于的二进制数的字典树,并记录各节点代表的元素...

2020-10-25

3 712