几个基础树上问题
一.喝牛奶
 l;考虑维护一个并查集，将互相连通且奶牛种类相同的农场放进同一个连通块中。只有两个点在同一个连通块中且该连通块中的牛奶种类与客人想喝的牛奶种类不同时才输出0.（若两点不在一个连通块中，可以得到两种牛奶，自然满足要求；若客人要求的牛奶种类与连通块中牛奶种类相同也满足要求）
#include<bits/stdc++.h>
using namespace std;
const int K = 100010;
int p[K];
char str[K];
int find(int x)
{if(p[x]!=x) p[x] = find(p[x]);else return p[x];
}
int main()
{int N,M;cin>>N>>M;for(int i = 1;i<=N;i++) p[i] = i;for(int i = 1;i<=N;i++) cin>>str[i];for(int i = 1;i<=N-1;i++){int X,Y;cin>>X>>Y;if(str[X]==str[Y]) p[find(X)] = find(Y);}while(M--){int A,B;char C;cin>>A>>B>>C;if(find(A)==find(B)&&str[A]!=C) cout<<"0";else cout<<"1";}return 0;
}
二.LCA
首先我们介绍一下什么是LCA。LCA全称为“lowest commen ancestor”，即最近公共祖先。最近公共祖先的定义如图。
一个节点到根节点路径上所有的点（包括它自身）被称为该点的祖先。最近公共祖先就是两个点的公共祖先中深度最大的那个（若两点相同，它们的最近公共祖先就是它们自身）。如图中3号点与5号点的最近公共祖先就是3本身，3号点和1号点的最近公共祖先是根节点。为了方便，以下我们约定根节点深度为1，0号节点（根节点上层的所有不存在的节点）深度为0。那么该如何寻找最近 公共祖先呢？
二.1.朴素LCA算法
其中一个点向根节点走，每走到一个点就标记一个（自身也要标记）。然后另外一个点也向根节点出发，当它第一次走到标记点，这个标记点就是最近公共祖先。
二.2.倍增LCA算法（log时间复杂度）
分为两步。（1）较深的点跳到较浅的点的同一层。
（2）两个点一起向上跳到最近公共祖先的下一层。需要注意的是，这两次跳跃的步长都是2的整数次幂。为此我们要预处理两个数组，第一个是depth，记录每个节点的深度信息；第二个是fa，fa[i][j]表示从编号为i的点向上跳2^j步到达的点的编号。跳跃时，我们从2的高次幂步长开始跳。比如两个点之间相差了11曾层，我们就先跳8层，再跳2层，最后跳一层；两个点在同一层后，如果离最近公共祖先是11层，我们也先跳8层，再跳2层。接下来让我们看看具体的代码实现吧！
#include<bits/stdc++.h>
using namespace std;
const int N = 40010;
//因为是无向树，两个点之间要存两条边
const int M = N*2;
int n,m;
int h[N],e[M],ne[M],idx;
//2^15 = 32768；
int depth[N],fa[N][16];
//队列
int q[N];
void add(int x,int y)
{e[idx] = y;//这里写ne[x]就错了！因为不是插入到两个点中间！是新开一个点！比如5是一个父节点，3是一个已经有的子节点，如果这时候再插入1写成ne[idx] = ne[x]，会形成5->1->3！ne[idx] = h[x];h[x] = idx++;
}
void bfs(int root)
{memset(depth,0x3f,sizeof depth);depth[0] = 0;depth[root] = 1;//定义一个队列int hh = 0,tt = 0;q[0] = root;//不能写小于！否则无法进入循环！while(hh<=tt){//取出队头int t = q[hh++];//此时的ne指向的是同一层的节点！for(int i = h[t];i>=0;i = ne[i]){int j = e[i];//由于初始时设定depth为正无穷，大于说明没被遍历到if(depth[j]>depth[t]+1){depth[j] = depth[t]+1;q[++tt] = j;fa[j][0] = t;//不能写成k<=16！for(int k = 1;k<=15;k++)fa[j][k] = fa[fa[j][k-1]][k-1];}}}
}
int lca(int a,int b)
{//我们假设a在b的下面。如果在上面，就交换if(depth[a]<depth[b]) swap(a,b);for(int k = 15;k>=0;k--)//哨兵节点的好处在这里体现出来。如果a不小心跳到哨兵节点了，哨兵节点的深度是0,，不会比depth[b]大,a也就不会上跳。如果甚至连哨兵节点也跳出了，那么本来的depth值默认就是0，自然也不会往上跳if(depth[fa[a][k]]>=depth[b]) a = fa[a][k];if(a==b) return a;for(int k = 15;k>=0;k--){//如果跳出去，两个都是0，不会不相等，不执行条件后的语句//fa[a][k]!=fa[b][k]说明还没到公共祖先if(fa[a][k]!=fa[b][k]){//一起跳a = fa[a][k];b = fa[b][k];}}//退出循环，说明下一次fa[a][0]==fa[b][0]，那么此时a,b都在最近公共祖先下一层，返回它们的上一层就是最近公共祖先return fa[a][0];
}
int main()
{scanf("%d%d",&n,&m);//初始化根节点int root = 0;memset(h,-1,sizeof h);for(int i = 0;i<n;i++){int a,b;cin>>a>>b;if(b==-1) root = a;else add(a,b),add(b,a);}bfs(root);cin>>m;while(m--){int a,b;cin>>a>>b;int p = lca(a,b);if(p==a) cout<<"1";else if(p==b) cout<<"2";else cout<<"0";}return 0;
}
附：bfs模板——
1.将初始状态入队
2.遍历整个队列
while(head<tail)
{
3.利用产生式规则拓展出当前队列头节点关联的新节点head++;if(拓展出的新节点没有出现过){新节点入队tail++;if(新节点就是目标节点){做出相应的处理}}
}二.3.Tarjan算法（线性时间复杂度）
基本思想：在dfs过程中把点分成三类：（1）已经搜过且完成回溯的点；（2）正在搜索的点；（3）还未被搜索过的点。把所有的询问存进来，观察哪些询问是关于x与某点的最近公共祖先的，就合并那个点到父节点当中去。如图——
在搜索红色分支时，绿色的点是2类点，红色的点是1类点，黄色的点是0类点。我们可以发现，绿色点和红色点中某个点的最近公共祖先恰好是在绿色点在正在搜索路径中的祖宗节点！
小公式：树上两点之间的距离 = 它们各自到根节点的距离之和减去两倍最近公共祖先到根节点的距离。
#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
const int M = N*2;
typedef pair<int,int> PII;
//res存储每个询问的结果,sts数组用来存储每个节点属于哪一类，dist数组存储某点到根节点的距离,p数组记录父节点信息
int h[N],e[M],ne[M],w[M],p[N],res[N],st[N],dist[N],idx,n,m;
//query.first存储与当前查询的点相关的另外一个点，second存查询编号
vector<PII>query[N];
void add(int a,int b,int c)
{e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}
void dfs(int u,int fa)
{for(int i = h[u];i>=0;i = ne[i]){int j = e[i];//这时候在往上搜了，但是我们要往下搜if(j==fa) continue;//子节点的距离等于父节点的距离加上这条边dist[j] = dist[u] + w[i];dfs(j,u);}
}
int find(int x)
{if(x!=p[x]) p[x] = find(p[x]);else return p[x];
}
//可以随便选一个点作为根节点
void tarjan(int u)
{//当前正在搜的点是第二类点st[u] = 1;//遍历与u相关的所有的邻点for(int i = h[u];i>=0;i = ne[i]){int j = e[i];//如果j没有被遍历过我们就遍历它if(!st[j]){tarjan(j);//把j合并到u里面去p[j] = u;}}//遍历所有与u有关的查询for(auto item:query[u]){//节点编号int y = item.first;//查询编号int id = item.second;//2用来表示已经遍历过且回溯过的点if(st[y]==2){//最近公共祖先是y在并查集中的祖宗节点int anc = find(y);res[id] = dist[u]+dist[y]-dist[anc]*2;}}//当前这个点已经被遍历过st[u] = 2;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i = 0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}for(int i = 0;i<m;i++){int a,b;cin>>a>>b;if(a!=b){query[a].push_back(b,i);query[b].push_back(a,i);}}for(int i = 1;i<=n;i++) p[i] = i;//求一下每个点与1号点之间的距离，第二个参数表示fatherdfs(1,-1);tarjan(1);for(int i = 0;i<m;i++) cout<<res[i]<<endl;return 0;
}
我们要找到这样一个点，将这个点删除以后这棵树分成的所有子树的节点数的最大值最小。详情请见代码注释——
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
//son[x][y]表示节点x的第y个儿子
vector<int> son[N];
//tot[i]表示以i为根节点的子树（包括i）的节点个数，F[i]表示删除节点i后得到的所有子树的节点数的最大值。
int tot[N],F[N],n;
int get_subNodeNumber(int k)
{
//判断是否已经到达叶子节点if(son[k].size()==0) return 1;else{//递归，以该点为根的字数大小等于1加上它的各个子树大小的和int res = 1;for(int j = 0;j<son[k].size();j++)res+=get_subNodeNumber(son[k][j]);return res;}
}
//寻找平衡点
int search(int root)
{for(int i = 1;i<=n;i++){int maxi = -1;//找到该点的所有子树的节点数的最大值for(int j = 0;j<son[i].size();j++)maxi = max(maxi,tot[son[i][j]]);//不是该点的子节点的所有节点成为一棵完整的树F[i] = max(n-tot[i],maxi);}//寻找平衡点int Fmin = 0x3f3f3f3f;for(int i = 1;i<=n;i++)Fmin = min(Fmin,F[i]);int tag = 0;for(int i = 1;i<=n;i++)if(F[i]==Fmin) tag = i;return tag;
}
int main()
{cin>>n;//寻找根的一个巧妙方法。因为这里限定a为父节点b为子节点，把所有的子节点编号减去就是没有父节点的点，就是根。int root = n*(n+1)/2;for(int i = 0;i < n-1;i++){int a,b;cin>>a>>b;son[a].push_back(b);root-=b;}for(int i = 1;i<=n;i++) tot[i] = get_subNodeNumber(i);cout<<search(root)<<' '<<F[search(root)]<<endl;return 0;
}
dfs写法——
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> son[N];
int tot[N],F[N],n;
void dfs(int k)
{
//赋初值，不用担心死递归tot[k] = 1;for(int j = 0;j<son[k].size();j++){dfs(son[k][j]);tot[k]+=tot[son[k][j]];}
}
int search(int root)
{for(int i = 1;i<=n;i++){int maxi = -1;for(int j = 0;j<son[i].size();j++)maxi = max(maxi,tot[son[i][j]]);F[i] = max(n-tot[i],maxi);}int Fmin = 0x3f3f3f3f;for(int i = 1;i<=n;i++)Fmin = min(Fmin,F[i]);int tag = 0;for(int i = 1;i<=n;i++)if(F[i]==Fmin) tag = i;return tag;
}
int main()
{cin>>n;int root = n*(n+1)/2;for(int i = 0;i < n-1;i++){int a,b;cin>>a>>b;son[a].push_back(b);root-=b;}dfs(root);cout<<search(root)<<' '<<F[search(root)]<<endl;return 0;
}
简单的贪心或者二分图染色都是不对的。例如——
蓝色表示选，红色表示不选。我们先假定所有点的HIHI值都为1。我们明显有更好的选法，那就是选第二层的前三个+第三层的所有。父节点选不选是子节点选不选的因素因此，因此要把它放到状态转移方程中。如果父节点选了，子节点不能选；如果父节点不选，子节点选择HIHI值和最大的那种情况。代码如下——
#include<bits/stdc++.h>
using namespace std;
const int K = 6010;
vector<int> son[K];
//F[i][0]表示不选i点时，i点及其子树能得到的最大HIHI值；F[i][1表示选i点时，i点及其子树能得到的最大HIHI值。
int HIHI[K],F[K][2];
void dfs(int k)
{
//赋初值，不会造成死递归F[k][0] = 0;F[k][1] = HIHI[k];for(int j = 0;j<son[k].size();j++){//要记得先算出前面的结果dfs(son[k][j]);F[k][0]+=max(F[son[k][j]][0],F[son[k][j]][1]);F[k][1]+=F[son[k][j]][0];}
}
int main()
{int N;cin>>N;for(int i = 1;i<=N;i++) cin>>HIHI[i];int root = N*(N+1)/2;for(int i = 1;i<=N-1;i++){int L,K;cin>>L>>K;son[K].push_back(L);root-=L;}dfs(root);cout<<max(F[root][0],F[root][1]);
}
&bbsp; 该点放不放士兵受到该点父节点和子节点的影响。F[i][0]表示该点放士兵的情况下，覆盖以该点为根节点的子树（包括该点）所需的最少士兵；F[i][1]表示该点不放士兵，该点靠其某个子节点覆盖的情况；F[i][2]表示该点不放士兵，该点被其父节点覆盖的情况。这里F[i][1]的转移方程较为棘手。我们具体该选择哪一个子节点呢？如果存在某个子节点的选比不选需要的士兵数少，那么我们就选它，其它的点都选较少士兵的那种情况就好了；如果所有子节点都是选比不选需要的士兵多，那我们就都先不选，然后选择那个从不选到选所需增加的士兵数最少的节点。代码如下——
#include<bits/stdc++.h>
using namespace std;
const int K = 10010;
vector<int> son[K];
int F[K][3],N;
void dfs(int k,int fa)
{F[k][0] = 1;F[k][1] = 0;F[k][2] = 0;int inc = 0x3f3f3f3f;for(int j = 0;j<son[k].size();j++){if(son[k][j]==fa) continue;dfs(son[k][j],k);F[k][0] += min(min(F[son[k][j]][0],F[son[k][j]][1]),F[son[k][j]][2]);F[k][2] += min(F[son[k][j]][0],F[son[k][j]][1]);F[k][1] += min(F[son[k][j]][0],F[son[k][j]][1]);inc = min(F[son[k][j]][0] - F[son[k][j]][1],inc);}if(inc<0) inc = 0;F[k][1]+=inc;
}
int main()
{cin>>N;int root = N*(N+1)/2;for(int i = 1;i<=N-1;i++){int A,B;cin>>A>>B;son[A].push_back(B);son[B].push_back(A);}dfs(1,0);cout<<min(F[1][0],F[1][1]);
}
博主的思路详见代码注释。过了样例但是内存超限了，有没有人教教呜呜呜——
#include<bits/stdc++.h>
using namespace std;
const int T = 110;
//a[x][y]表示节点x和节点y之间的树枝上的苹果数量
int a[T][T],N,Q;
//F[i][j]表示以i为根节点的子树在留下y根枝条的情况下可以得到的最大苹果数量
vector<int>F[T];
//建无根树，最多可能连三条边
vector<int> son[4];
void dfs(int k,int fa)
{for(int i = 0;i<N+2;i++)for(int j = 0;j<N+2;j++)F[i].push_back(0);if(son[k].size()==1){return;}for(int l = 0;l<=N-1;l++){if(l>=1){F[k][l] = 0;for(int j = 0;j<son[k].size();j++){if(son[k][j]==fa) continue;dfs(son[k][j],k);//左右子树中保留一棵的情况F[k][l] = max(F[son[k][j]][l-1]+a[k][son[k][j]],F[k][l]);}if(l>=2){ for(int t = 0;t<=l-2;t++){vector<int> tmp;for(int j = 0;j<son[k].size();j++)if(son[k][j]!=fa) tmp.push_back(j);//找到真正的子节点pair<int,int> p = {tmp[0],tmp[1]};//左子树保留t根枝条，右子树保留l-t-2根枝条F[k][l] = max(F[k][l],F[son[k][p.first]][l-t-2]+F[son[k][p.second]][t]+a[k][son[k][p.first]]+a[k][son[k][p.second]]);}}}else{F[k][l] = 0;}}
}
int main()
{cin>>N>>Q;for(int i = 1;i<=N-1;i++){int x,y,z;cin>>x>>y>>z;a[x][y] = z;a[y][x] = z;son[x].push_back(y);son[y].push_back(x);}dfs(1,-1);cout<<F[1][Q];return 0;
}
好啦，以上就是本篇文章的全部内容。如果你感到对自己有帮助的话，就请支持一下博主吧！
