换根dp题集

dp题集"/>

换根dp题集

题目链接

题意：给你一棵树，按顺序输出以每个顶点为根节点，到任意点的边权和最大，输出这个最大值。

思路：换根dp，两遍dfs，第一个dfs求出以这个点为根节点，子树的最大边权值，保存在d数组中。第二个dfs1，首先算出以u节点为根节点的dp值，保存在ans数组里，然后求出u节点的儿子的前缀dp值保存在suf数组中，再求出u节点儿子的后缀dp值保存在x中，那么换根后的u节点的dp值，d【u】=max（suf【u】【i】，x）。

#include<bits/stdc++.h>
#define pi pair<int,int>
using namespace std;
#define mk make_pair
#define ll long long
const int maxn=10010;
vector<pi>G[maxn];
vector<long long>suf[maxn];
ll ans[maxn];
ll d[maxn];
void dfs(int u,int fa)
{d[u]=0;for(auto it:G[u]){int v=it.first;int w=it.second;if(v==fa)continue;dfs(v,u);d[u]=max(d[u],d[v]+w);}
}
void dfs1(int u,int fa)
{suf[u].push_back(0);d[u]=0;for(auto it:G[u]){int v=it.first;int w=it.second;d[u]=max(d[u],d[v]+w);suf[u].push_back(d[u]);}ans[u]=d[u];long long x=0;for(int i=G[u].size()-1;i>=0;i--){int v=G[u][i].first;int w=G[u][i].second;d[u]=max(suf[u][i],x);x=max(x,d[v]+w);if(v==fa)continue;dfs1(v,u);}
}
int main()
{int n,u,w;while(~scanf("%d",&n)){for(int i=1;i<=n;i++)G[i].clear(),suf[i].clear();for(int i=2;i<=n;i++){scanf("%d%d",&u,&w);G[u].push_back(mk(i,w));G[i].push_back(mk(u,w));}dfs(1,0);dfs1(1,0);for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';}
}

 题目链接

题意：给你一棵树，有m个特殊点，问是否存在一个点，所有的特殊点到这和点的距离都相等。

思路：换根dp，首先我们设两个数组mx【maxn】，和mi【maxn】，分别代表离u节点的最远的特殊点和最近的特殊点，那么，如果存在一个点，他的mx【u】等于mi【u】，它即为答案。两次dfs，第一次求出以u为根节点，子树特殊点最远的点和最近的点，第二次dfs1算答案换根。

#include<bits/stdc++.h>
using namespace std;
#define pi pair<int,int >
#define mk make_pair
const int maxn=2e5+100;
vector<int>G[maxn];
vector<pi>pre[maxn];
const int inf=1e9;
int p[maxn],mx[maxn],mi[maxn],flag=0;
void dfs(int u,int fa)
{if(p[u])mx[u]=mi[u]=0;else mx[u]=-inf,mi[u]=inf;for(auto v: G[u]){if(v==fa)continue;dfs(v,u);mx[u]=max(mx[u],mx[v]+1);mi[u]=min(mi[u],mi[v]+1);}
}
void dfs1(int u,int fa)
{if(flag)return ;if(p[u])mx[u]=mi[u]=0;else mx[u]=-inf,mi[u]=inf;pre[u].push_back(mk(mx[u],mi[u]));for(auto v : G[u]) {mx[u]=max(mx[u],mx[v]+1);mi[u]=min(mi[u],mi[v]+1);pre[u].push_back(mk(mx[u],mi[u]));}if(mx[u]==mi[u]){flag=u;return ;}int lax=-inf,lai=inf;for(int i=G[u].size()-1;i>=0;i--){int v=G[u][i];int t1=pre[u][i].first;int t2=pre[u][i].second;mx[u]=max(t1,lax);mi[u]=min(t2,lai);lax=max(lax,mx[v]+1);lai=min(lai,mi[v]+1);if(v==fa)continue;dfs1(v,u);}
}
int main()
{int n,m,u,v;scanf("%d%d",&n,&m);for(int i=1;i<n;i++) {scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=m;i++){scanf("%d",&u);p[u]=1;}dfs(1,0);dfs1(1,0);if(flag)puts("YES"),printf("%d\n",flag);else puts("NO");
}

 

题意：给你一棵树，求一个度数大于1的点，满足它的所有的子树都有相同的结构，输出这个点的最大的度数。

思路，要满足结构相同可以用hash。然后换根dp，第一遍dfs求出以这个点为根节点的子树的hash值，我们需要排序，对hash值进行排序，第二遍dfs换根。

    #include<bits/stdc++.h>using namespace std;const int maxn=4005;const int mod1=10000007,mod2=998244353;int ans = -1;int p[maxn],p1[maxn];struct node{int h1,h2,len;}d[maxn];vector<node> S[maxn];vector<int> G[maxn];bool cmp(int a,int b){return d[a].h1<d[b].h1 || (d[a].h1==d[b].h1&&d[a].h2<d[b].h2);}node merge(node a,node b){node tmp;tmp.h1 = (1ll*a.h1*p[b.len] + b.h1) % mod1;tmp.h2 = (1ll*a.h2*p1[b.len] + b.h2) %mod2;tmp.len=a.len+b.len;return tmp;}void dfs(int u,int fa){d[u]=node{1,1,1};for(auto v : G[u])if(v != fa) dfs(v,u);sort(G[u].begin(),G[u].end(),cmp);for(auto v: G[u])if(v!=fa)d[u]=merge(d[u],d[v]);}void dfs1(int u,int fa){d[u]=node{1,1,1};sort(G[u].begin(),G[u].end(),cmp);S[u].push_back(node{1,1,1});node tmp{0,0,0};int flag=1;for(auto v : G[u]){d[u] = merge(d[u],d[v]);if(tmp.len==0)tmp=d[v];else if(d[v].h1!=tmp.h1 || d[v].h2!=tmp.h2)flag=0;S[u].push_back(d[u]);}if(flag&&G[u].size()>1){ans=max(ans,(int)G[u].size());}node t=node{0,0,0};for(int i=G[u].size()-1;i>=0;i--){d[u]=merge(S[u][i],t);t=merge(d[G[u][i]],t);if(G[u][i]!=fa)dfs1(G[u][i],u);}}int main(){p[0]=p1[0]=1;for(int i=1;i<maxn;i++){p[i]=1ll*p[i-1]*40007%mod1;p1[i]=1ll*p1[i-1]*40013%mod2;}int n,u,v;cin>>n;for(int i=1;i<n;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}dfs(1,0);dfs1(1,0);printf("%d\n",ans);}