客户关系管理系统(Customer Relationship Management)将客户看作是企业的一项重要资产,客户关怀是CRM的中心,其目的是与客户建立长期和有效的业务关系,在与客户的每个“接触点”上都更加接近客户.了解客户,最大限度的增加利润.CRM的核心是客户价值管理,它将客户价值分为既成价值.潜在价值和模型价值,通过“一对一”的营销原则,满足不同价值客户的个性化需求,提高客户忠诚度和保有率,实现客户价值持续贡献,从而全面提升企业盈利能力. CRM实际上是一个概念,也是一种理念:同时,

题目描述 小强要在N个孤立的星球上建立起一套通信系统.这套通信系统就是连接N个点的一个树. 这个树的边是一条一条添加上去的.在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量. 例如,在上图中,现在一共有了5条边.其中,(3,8)这条边的负载是6,因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8). 现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的询问. 输入 第一行包含两个整数N,Q,表示星球的

题目描述 小强要在N个孤立的星球上建立起一套通信系统.这套通信系统就是连接N个点的一个树. 这个树的边是一条一条添加上去的.在某个时刻,一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量. 例如,在上图中,现在一共有了5条边.其中,(3,8)这条边的负载是6,因 为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8). 现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的 询问. 输入 第一行包含两个整数N,Q,表示

题目描述 给出一棵树和一个点对集合S,多次改变这棵树的形态.在集合中加入或删除点对,或询问集合内的每组点对之间的路径是否都经过某条给定边. 输入 输入的第一行包含一个整数 id,表示测试数据编号,如第一组数据的id=1,样例数据的 id 可以忽略.输入的第二行包含两个整数 n,m,分别表示图中的点数,以及接下来会发生的事件数,事件的定义下文中会有描述.初始时 S 为空.接下来 n−1 行,每行两个正整数 x,y,表示点 x 和点 y 之间有一条无向边.接下来 m 行,每行描述一个事件,每行的第一

题目描述 在X星球上有N个国家,每个国家占据着X星球的一座城市.由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的. X星球上战乱频发,如果A国打败了B国,那么B国将永远从这个星球消失,而B国的国土也将归A国管辖.A国国王为了加强统治,会在A国和B国之间修建一条公路,即选择原A国的某个城市和B国某个城市,修建一条连接这两座城市的公路. 同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是指需要经过公路的条数,如果有多个这样的城市,编号最小

[BZOJ3510]首都 Description 在X星球上有N个国家,每个国家占据着X星球的一座城市.由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的. X星球上战乱频发,如果A国打败了B国,那么B国将永远从这个星球消失,而B国的国土也将归A国管辖.A国国王为了加强统治,会在A国和B国之间修建一条公路,即选择原A国的某个城市和B国某个城市,修建一条连接这两座城市的公路. 同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是指需要经过公

题目 [题目描述] 小强要在 $N$ 个孤立的星球上建立起一套通信系统.这套通信系统就是连接 $N$ 个点的一个树.这个树的边是一条一条添加上去的.在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量. 例如,在上图中,现在一共有五条边.其中,$(3,8)$ 这条边的负载是 $6$,因为有六条简单路径 $2-3-8,\ 2-3-8-7,\ 3-8,\ 3-8-7,\ 4-3-8,\ 4-3-8-7$ 路过了 $(3,8)$. 现在,你的任务就是随着边的添加,动态的回答小强

Code: #include<bits/stdc++.h> #define maxn 150000 #define ll long long #define inf 2147483647000 using namespace std; #define getset chil[x].empty()?inf:*chil[x].begin() void setIO(string s) { string in=s+".in", out=s+".out"; fre

用 set 维护子树信息,细节较多. Code: #include <cstring> #include <cstdio> #include <algorithm> #include <set> #include <string> #define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdou

这个题目的关键就是判断 大爷所有可能会走的路 会不会经过询问的边. 某一条路径经过其中的一条边, 那么2个端点是在这条边的2测的. 现在我们要判断所有的路径是不是都经过 u -> v 我们以u为根节点, 如果所有的路劲的起点 有且仅有一个点在 v 的子树内 我们就可以知道这个边是合法的. 那么我们每次增加路劲之后, 都在2个端点都亦或上某一个值, 每次判断的时候都判断这个v的子树内整颗树的亦或和是不是等于整体亦或和.如果是 那就说明合法. 现在我们用lct维护这个树. 在这个地方我们需要用lct

链接:https://loj.ac/problem/2230 思路: 设立siz数组保存虚点信息,sum表示总信息 维护子树信息link操作和access操作需要进行一些改动 可参考博客:https://www.cnblogs.com/GXZlegend/p/7061458.html 实现代码; #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include&l

题目传送门 https://lydsy.com/JudgeOnline/problem.php?id=3510 题解 首先每一个连通块的首都根据定义,显然就是直径. 然后考虑直径的几个性质: 定义:删去这个点以后剩下的连通块最大的最小的点为重心. 一棵树最多只能有两个相邻的直径: 一棵树的重心到一棵树中所有点的距离和最小.(这个也是题目的条件转化为重心的原因) 两棵树的并的重心在两棵树各自的重心的连线上. 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置. 有了这些性质,我们可以发现,

\(LCT\)维护子树信息学习笔记 昨天\(FDF\)好题分享投了 \([ZJOI2018]\)历史 这题. 然后我顺势学学这个姿势. 结果调了一年...于是写个笔记记录一下. 基本原理 比较显然地,虽然父子关系在不断变化,但是重链与重链之间的连接是不变的.换句话说,一个点的某个虚儿子也许并不是他在原树中的某个儿子,但是这个点总和上来的信息是这整棵子树的. 所以我们定义这个点总和的信息(记为\(siz\))为总和该子树的所有信息, 然后记\(fsz\)为虚儿子的总和信息,\(val\)为单点信息

可以作为 LCT 维护子树信息的模板,写的还是比较优美的. 本地可过,bzoj 时限太紧,一直 TLE #include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout) #define maxn 100002 #define inf 100000000 #define isrt(x) (!

这道题思路方面就不多讲了,主要是通过这题学一下lct维护子树信息. lct某节点u的子树信息由其重链的一棵splay上信息和若干轻儿子子树信息合并而成. splay是有子树结构的,可以在rotate,access的时候由儿子update到父亲,而轻儿子的信息update不上来,需要另外记一下. 记sum[x]为我们要求的子树信息,xu[x]为x的轻儿子的子树信息. (即,xu[x]由轻儿子的sum更新,sum[x]由xu[x]和splay子树上的儿子的sum更新. 这样我们就可以完整地用lct维

QWQ 这个题目是LCT维护子树信息的经典应用 根据题目信息来看,对于一个这条边的两个端点各自的\(size\)乘起来,不过这个应该算呢? 我们可以考虑在LCT上多维护一个\(xv[i]\)表示\(i\)的虚子树的子树和,然后维护\(sum[i]\)表示\(i\)的虚+实子树之和. 那么对于一个点\(x\),他在原树上的字数大小就应该是$$size = xv[x]+sum[ch[x][1]]+1$$ 这是个经典套路! 对于这个题来说,我们可以通过\(split(x,y)\),然后\(ans\)就

综合项目需求 一.系统整体功能 系统需支持以下功能: 维护学生信息.老师信息和成绩信息 支持按多种条件组合查询学生信息和成绩信息 学生 Student(id,班级id,学号,姓名,性别,电话,地址,出生日期,民族,家长电话1,家长电话2) 老师 Teacher(id,工号,姓名,性别,电话,类型(班主任.讲师)) 班级 Class(id,班级名称,讲师id,班主任id) 课程 Subject(id,课程名称.课程简介) 成绩 Score(id,stu_id,sub_id,卷面成绩,项目成绩,平时

题面 没有权限号的可以去LOJ Sol 大家都知道,\(LCT\)上有许多实边和虚边 实边就是每棵\(Splay\)上的既认父亲又认儿子的边 虚边就是\(Splay\)和\(Splay\)之间只认父亲的的边 那么每个点就有它的虚儿子和实儿子,实际上虚儿子才是它在\(LCT\)维护的树上的真正的儿子 当你\(Access(x)\)时,\(x\)的虚儿子加上它自己就是它子树的信息 所以我们要维护每个点虚儿子的信息和LCT子树的信息(也就是虚儿子+实儿子+自己) 怎么维护? 你会发现这只会在\(Acc

有些题目,在要求支持link-cut之外,还会在线询问某个子树的信息.LCT可以通过维护虚边信息完成这个操作. 对于LCT上每个节点,维护两个两sz和si,后者维护该点所有虚儿子的信息,前者维护该点的所有信息和. 那么显然有:$si[x]=\sum sz[pson]$,$sz[x]=sz[lson]+sz[rson]+si[x]+v[x]$. 其中pson是虚儿子,lson,rson是LCT上的实儿子,v是节点本身的信息. 那么,考虑在哪些操作下需要更新这两个值. 1.access  每次将旧虚

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3779 调了很久……已经懒得写题解了.https://www.cnblogs.com/Zinn/p/10124183.html 线段树和LCT是分开的.线段树的子树一直是相对于 1 号点而言.线段树上维护的值总是相对于当前的 rt 的. 怎么保证一直是相对于当前 rt 的呢?发现如果 rt 和 rt' 之间的链上全是重边,则每个子树对于 rt 的答案和对于 rt' 的答案是一样的. 所以在换

Code: #include<bits/stdc++.h> #define maxn 200000 #define inf 1000000000 using namespace std; void setIO(string s) { string in=s+".in",out=s+".out"; freopen(in.c_str(),"r",stdin); } multiset<int>sonmax[maxn]; int