兰州网站建设方法,今天全球重大新闻,企业管理平台app,莆田市建设局网站之前都看过有换根dp#xff0c;一直不知道是啥意思#xff0c;本来弱弱树形dp都不太熟悉#xff0c;不过今天工数课的时候突然想看一下#xff0c;写个板子题练练吧。
对于我的理解#xff0c;换根的题目一般是根不确定#xff0c;而求得答案与根是谁有关#xff0c;而…之前都看过有换根dp一直不知道是啥意思本来弱弱树形dp都不太熟悉不过今天工数课的时候突然想看一下写个板子题练练吧。
对于我的理解换根的题目一般是根不确定而求得答案与根是谁有关而且通过暴力枚举每个点为根节点即可得到答案。 这时候如果我们发现当该点的信息能够通过父节点的信息递推出来那么我们可以考虑尝试换根dp毕竟换根dp的本质还是递推只不过通过父节点的信息递推本节点。
[POI2008]STA-Station
不难发现如果我们知道以父节点为根所有深度和那么该节点相对于父亲来说该节点子树的深度比以父节点为根时的深度要小1而不在该节点子树中的节点深度要比以父节点是根时的深度大1由此得出以下递推关系 fsonfun−sizeson−sizesonf_{son}f_un-size_{son}-size_{son}fsonfun−sizeson−sizeson
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
//#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N1000010;
int h[N],e[2*N],ne[2*N],idx;
int n;
ll dep[N];
int sz[N];
ll f[N];
int res1;
void dfs1(int u,int fa)
{sz[u]1;for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;dep[j]dep[u]1;dfs1(j,u); sz[u]sz[j];}
}
void dfs2(int u,int fa)
{for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;f[j]f[u]sz[1]-sz[j]-sz[j];if(f[j]f[res]) resj;dfs2(j,u);}}
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
int main()
{IO;int T1;//cinT;while(T--){cinn;memset(h,-1,sizeof h);for(int i1;in;i){int a,b;cinab;add(a,b),add(b,a);}dfs1(1,-1);for(int i1;in;i) f[1]dep[i];dfs2(1,-1);coutres\n;}return 0;
}
