精华内容
下载资源
问答
  • 省选模拟赛: 分析 考场上想出来了一个被卡常了的点分治的O(nlog2)O(nlog^2)O(nlog2)的做法,T到起飞。。 有一种假装好些好调的LCTLCTLCT做法。 因为LCTLCTLCT的辅助内维护的是一条链,而我们维护的是到...

    省选模拟赛:树

    在这里插入图片描述
    在这里插入图片描述

    分析

    考场上想出来了一个被卡常了的点分治的 O ( n l o g 2 ) O(nlog^2) O(nlog2)的做法,T到起飞。。
    有一种假装好些好调的 L C T LCT LCT做法。
    因为 L C T LCT LCT的辅助树内维护的是一条链,而我们维护的是到这条实链上的最浅和最深的节点到当前子树内的最远距离。
    考虑采用 r m x rmx rmx l m x lmx lmx分别表示最深和最浅, m x s mxs mxs表示最长链。
    既然是到当前子树内,那么肯定要用到子树信息。
    首先考虑实链上的转移,假设当前节点是 S p l a y Splay Splay树中的 p p p,那么 l s ls ls表示它在原树上的祖先, r s rs rs表示它在原树上的某条子树内的链。以 l m x lmx lmx的转移为例。
    l m x [ l s ] − > l m x [ p ] lmx[ls]->lmx[p] lmx[ls]>lmx[p]
    保留子树的答案,剩下只需要考虑过 p p p的路径。
    l m x [ r s ] + s u m [ l s ] + a [ p ] − > l m x [ p ] lmx[rs]+sum[ls]+a[p]->lmx[p] lmx[rs]+sum[ls]+a[p]>lmx[p]
    沿着实链走下去。
    再考虑虚子树的转移。我们需要得到的就是虚子树内深度最大的节点。考虑 l m x [ p ] lmx[p] lmx[p]的意义,实链上最浅的节点实际上也是原树上子树的根节点。所以 l m x [ p ] lmx[p] lmx[p]也可以作为子树信息,表示子树内最浅的节点到子树内一点最远距离。
    所以可以采用维护子树信息的操作。用一个set来维护。
    M i n ( s o n ) + a [ p ] + s u m [ l s ] − > l m x [ p ] Min(son)+a[p]+sum[ls]->lmx[p] Min(son)+a[p]+sum[ls]>lmx[p]
    走到 p p p后沿着虚子树走下去。
    r m x rmx rmx的转移是类似的,有了 l m x lmx lmx, r m x rmx rmx的信息, m x s mxs mxs稍微讨论一下转移即可。
    代码与常数均小的一个神仙做法。

    代码

    #include<bits/stdc++.h>
    #define ls ch[p][0]
    #define rs ch[p][1]
    const int N = 1e5 + 10, inf = 1e9;
    using std::max;
    typedef long long LL;
    typedef std::multiset<LL> MI;
    int ri() {
    	char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
    	for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
    }
    MI Chain[N], Path[N];
    int a[N], ch[N][2], fa[N], pr[N], to[N << 1], nx[N << 1], tp;
    LL sum[N], lmx[N], rmx[N], mxs[N], Ans;
    void add(int u, int v) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp;}
    void adds(int u, int v) {add(u, v); add(v, u);}
    bool wh(int p) {return ch[fa[p]][1] == p;}
    bool Ir(int p) {return ch[fa[p]][0] != p && ch[fa[p]][1] != p;}
    void Era(MI &s, int v) {
    	if(s.find(v) == s.end()) puts("ERRR");
    	s.erase(s.find(v));
    }
    void Era(int u, int v) {
    	Era(Chain[u], lmx[v]); Era(Path[u], mxs[v]);
    }
    void Ins(int u, int v) {
    	Chain[u].insert(lmx[v]); Path[u].insert(mxs[v]); 
    }
    LL fir(MI &s) {return s.size() ? *s.rbegin() : -inf;}
    LL sec(MI &s) {return s.size() > 1 ? *(++s.rbegin()) : -inf;}
    void Re(LL &a, LL b) {a = max(a, b);}
    void Up(int p) {
    	sum[p] = sum[ls] + sum[rs] + a[p];
    	LL cha = max(0LL, fir(Chain[p]));
    	LL L = max(cha, rmx[ls]) + a[p];
    	LL R = max(cha, lmx[rs]) + a[p];
    	lmx[p] = max(lmx[ls], sum[ls] + R);
    	rmx[p] = max(rmx[rs], sum[rs] + L);
    	mxs[p] = max(rmx[ls] + R, lmx[rs] + L);
    	Re(mxs[p], max(mxs[ls], mxs[rs]));
    	Re(mxs[p], fir(Path[p]));
    	Re(mxs[p], cha + sec(Chain[p]) + a[p]);
    	Re(mxs[p], cha + a[p]);
    }
    void Rotate(int p) {
    	int f = fa[p], g = fa[f], c = wh(p);
    	if(!Ir(f)) ch[g][wh(f)] = p; fa[p] = g;
    	ch[f][c] = ch[p][c ^ 1]; if(ch[f][c]) fa[ch[f][c]] = f;
    	ch[p][c ^ 1] = f; fa[f] = p; Up(f);
    }
    void Splay(int p) {
    	for(;!Ir(p); Rotate(p))
    		if(!Ir(fa[p])) Rotate(wh(fa[p]) == wh(p) ? fa[p] : p);
    	Up(p);
    }
    void Access(int u) {
    	for(int p = u, pr = 0; p; pr = p, p = fa[p]) {
    		Splay(p);
    		if(pr) Era(p, pr);
    		if(rs) Ins(p, rs);
    		rs = pr; 
    		Up(p);		
    	}
    	Splay(u);
    }
    void Change(int u, int v) {Access(u); a[u] = v; Up(u); Ans = mxs[u];}
    LL Query(int p) {
    	Access(p); LL res = 0;
    	LL cha = max(0LL, fir(Chain[p]));
    	LL L = max(cha, rmx[ls]) + a[p];
    	LL R = max(cha, lmx[rs]) + a[p];
    	res = max(rmx[ls] + R, lmx[rs] + L);
    	Re(res, cha + sec(Chain[p]) + a[p]);
    	Re(res, cha + a[p]);
    	return res;
    }
    void Dfs(int u) {
    	for(int i = pr[u]; i; i = nx[i])
    		if(to[i] != fa[u]) {
    			fa[to[i]] = u;
    			Dfs(to[i]);
    			Ins(u, to[i]);
    		}
    	Up(u);
    }
    int main() {
    	freopen("tree.in","r",stdin);
    	freopen("tree.out","w",stdout);
    	int n = ri(), m = ri();
    	for(int i = 1;i < n; ++i)
    		adds(ri(), ri());
    	for(int i = 1;i <= n; ++i)
    		a[i] = ri();
    	for(int i = 0;i <= n; ++i)
    		lmx[i] = rmx[i] = mxs[i] = -inf;
    	Dfs(1); Ans = mxs[1];
    	for(;m--;) {
    		int op = ri(), u;
    		if(op == 1) printf("%I64d\n", Ans);
    		else if(op == 2) printf("%I64d\n", Query(ri()));
    		else u = ri(), Change(u, ri());
    	}
    	return 0;
    }
    
    展开全文
  • 树木直径生长的实时精密测量装置
  • 鹅掌楸树木直径动态变化及其对气象因子的响应
  • 1. 定义邻接表存储的图类。 2. 实验验证如下算法的正确性、各种功能及指标: 1) 创建一个邻接表存储的图; 2) 返回图中指定边的权值; 3)插入操作:向图中插入一条边;...设计并实现一个算法,求自由直径
  • 行业分类-作业装置-一种测量树木直径给浇灌水管开孔的打孔设备.7z
  • nnn 个点的一棵,每个点初始为 000,支持两种操作,第一种操作 C xC \ xC x,表示将第 xxx 个点取反,即 111 变 000,000 变 111。第二种操作为 GGG,表示查询两个相距最远的 000 点距离。(1≤n≤105,1...

    题意:

    n n n 个点的一棵树,每个点初始为 0 0 0,支持两种操作,第一种操作 C   x C \ x C x,表示将第 x x x 个点取反,即 1 1 1 0 0 0 0 0 0 1 1 1。第二种操作为 G G G,表示查询两个相距最远的 0 0 0 点距离。 ( 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 5 ∗ 1 0 5 ) (1\leq n\leq 10^5,1\leq m\leq 5*10^5) (1n105,1m5105)


    思路:

    这道题的做法有括号序列、动态点分治、线段树维护直径。此处只介绍线段树维护直径的做法。

    首先我们求一个 d f s dfs dfs 序,然后在 d f s dfs dfs 序上建线段树,对于线段树的每个区间,我们维护两个点表示在这个区间中相距最远的两个 0 0 0 点。区间合并时我们只需要取出这两个区间所维护的点,然后对这四个点两两求距离更新答案即可。

    这样做的原因在于对于两个子树来说,每个子树都有一条属于该子树的直径,则两个子树合并后的新直径必定是从原来两个子树中的 4 4 4 个点中选取 2 2 2 个点作为答案。

    大致思路就是这样,具体细节见代码。


    代码:

    #include <bits/stdc++.h>
    #define rep(i,a,b) for(int i = a; i <= b; i++)
    typedef long long ll;
    const int N = 1e5+100;
    using namespace std;
    
    int n,m,dis[N],tot,head[N],f[N][25],dfn[N],rk[N],flag[N],T;
    pair<int,int> sgt[4*N];
    struct Edge{
    	int to,next;
    }e[2*N];
    
    inline void add(int x,int y){
    	e[++tot].to = y, e[tot].next = head[x], head[x] = tot;
    }
    
    void dfs(int x,int fa){
    	dis[x] = dis[fa]+1; f[x][0] = fa; dfn[x] = ++tot; rk[tot] = x;
    	for(int i = 1; (1<<i) <= dis[x]; i++)
    		f[x][i] = f[f[x][i-1]][i-1];
    	for(int i = head[x]; i; i = e[i].next){
    		int y = e[i].to;
    		if(y == fa) continue;
    		dis[y] = dis[x]+1; dfs(y,x);
    	}
    }
    
    inline int lca(int x,int y){
    	if(dis[x] > dis[y]) swap(x,y);
    	for(int i = T; i >= 0; i--)
    		if(dis[f[y][i]] >= dis[x]) y = f[y][i];
    	if(x == y) return x;
    	for(int i = T; i >= 0; i--)
    		if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    	return f[x][0];
    }
    
    inline int dist(int x,int y){
    	if(x == 0 && y == 0) return -1;
    	if(x == 0 || y == 0) return 0;
    	return dis[x]+dis[y]-2*dis[lca(x,y)];
    }
    
    inline pair<int,int> pushUp(pair<int,int> x,pair<int,int> y){
    	int a[5],res = 0,cnt = 0,tmp; pair<int,int> base = make_pair(0,0); a[0] = 0;
    	if(x.first && flag[x.first]) a[++cnt] = x.first;
    	if(x.second && flag[x.second]) a[++cnt] = x.second;
    	if(y.first && flag[y.first]) a[++cnt] = y.first;
    	if(y.second && flag[y.second]) a[++cnt] = y.second;
    	rep(i,1,cnt-1)
    		rep(j,i+1,cnt)
    			if((tmp=dist(a[i],a[j])) > res)
    				res = tmp, base = make_pair(a[i],a[j]);
    	if(res == 0) base = make_pair(a[cnt],a[cnt]);
    	return base;
    }
    
    inline void build(int now,int l,int r){
    	if(l == r) sgt[now] = make_pair(rk[l],rk[l]), flag[rk[l]] = 1;
    	else{
    		int mid = (l+r)>>1;
    		build(now<<1,l,mid); build(now<<1|1,mid+1,r);
    		sgt[now] = pushUp(sgt[now<<1],sgt[now<<1|1]);
    	}
    }
    
    inline void update(int now,int l,int r,int pos){
    	if(l == r){
    		flag[rk[l]] ^= 1;
    		if(flag[rk[l]]) sgt[now] = make_pair(rk[l],rk[l]);
    		else sgt[now] = make_pair(0,0);
    		return;
    	}
    	int mid = (l+r)>>1;
    	if(pos <= mid) update(now<<1,l,mid,pos);
    	else update(now<<1|1,mid+1,r,pos);
    	sgt[now] = pushUp(sgt[now<<1],sgt[now<<1|1]);
    }
    
    int main()
    {
    	scanf("%d",&n); 
    	tot = 1; T = (int)(log(n)/log(2))+1;
    	rep(i,1,n-1){
    		int a,b; scanf("%d%d",&a,&b);
    		add(a,b); add(b,a);
    	}
    	tot = 0; dfs(1,0); build(1,1,n);
    	scanf("%d",&m);
    	while(m--){
    		char op[10]; scanf("%s",op);
    		if(op[0] == 'C'){
    			int x; scanf("%d",&x); 
    			update(1,1,n,dfn[x]);
    		}
    		else printf("%d\n",dist(sgt[1].first,sgt[1].second));
    	}
    	return 0;
    }
    
    展开全文
  • 直径

    千次阅读 多人点赞 2019-04-09 22:44:58
    直径上最远两点(叶子结点)的距离。那么怎么求直径呢? 方法一:暴力求解,从每个点开始遍历图,可以得到每个点v所在的最长路径max1和次长路径max2,注意的是最长路径和次长路径除了点v没有其他公共...

    树的直径:树上最远两点(叶子结点)的距离。那么怎么求树的直径呢?

    1. 方法一:暴力求解,从每个点开始遍历图,可以得到每个点v所在的最长路径max1和次长路径max2,注意的是最长路径和次长路径除了点v没有其他公共结点。如下图所示,经过点A的最长路径应该是下图左所示的路径,而非下图右所示的路径,通过A的最长路径必须是来自不同分支。方法一,暴力破解,每个点做一趟DFS的话,时间复杂度为 O ( n 2 ) O(n^2) O(n2)
      在这里插入图片描述
    2. 方法二:从树上任意点u开始DFS(BFS)遍历图,得到距离u最远的结点v,然后从v点开始DFS遍历图,得到距离v最远的结点w, 则v、w之间的距离就是树的直径。
      证明:假设路径v-w为树的直径
      1)u位于v-w所在的路径上,如下图左图所示,那么从u点做DFS能访问到的最远点必然是v或w, 否则假设访问到的最远点为x, 如下图所示,有 d i s t ( u , x ) ≥ d i s t ( u , v ) , d i s t ( u , x ) ≥ d i s t ( u , w ) dist(u,x) \geq dist(u,v), dist(u,x) \geq dist(u,w) dist(u,x)dist(u,v)dist(u,x)dist(u,w), 分两种情况讨论:
      a) 如果只取大于号, d i s t ( u , x ) &gt; d i s t ( u , v ) , d i s t ( u , x ) &gt; d i s t ( u , w ) dist(u,x) &gt; dist(u,v) , dist(u,x) &gt; dist(u,w) dist(u,x)>dist(u,v)dist(u,x)>dist(u,w)
      那么 d i s t ( u , x ) + d i s t ( u , v ) = d i s t ( v , x ) &gt; d i s t ( u , v ) + d i s t ( u , w ) = d i s t ( v , w ) dist(u,x) + dist(u,v) = dist(v,x) &gt; dist(u,v) + dist(u,w) = dist(v,w) dist(u,x)+dist(u,v)=dist(v,x)>dist(u,v)+dist(u,w)=dist(v,w), 那么v-w不是树的是直径,跟假设矛盾。
      b) 如果取大于等于号, d i s t ( u , x ) ≥ d i s t ( u , v ) , d i s t ( u , x ) ≥ d i s t ( u , w ) dist(u,x) \geq dist(u,v) , dist(u,x)\geq dist(u,w) dist(u,x)dist(u,v)dist(u,x)dist(u,w)
      假设 d i s t ( u , x ) = d i s t ( u , v ) dist(u,x) = dist(u,v) dist(u,x)=dist(u,v) 那么 d i s t ( x , w ) = d i s t ( v , w ) dist(x,w) = dist(v,w) dist(x,w)=dist(v,w), 这样也没问题,树的直径不唯一而已,那么x依然位于树的直径的一个端点上。
      2)u不位于v-w所在的路径上,如下图右图所示,那么有 d i s t ( u , x ) &gt; d i s t ( u , y , v ) , d i s t ( u , x ) &gt; d i s t ( u , y , w ) dist(u,x) &gt; dist(u,y,v) , dist(u,x) &gt; dist(u,y,w) dist(u,x)>dist(u,y,v)dist(u,x)>dist(u,y,w), 这里y是u到路径[v-w]的任意点,那么就有 d i s t ( u , x ) + d i s t ( u , y , w ) = d i s t [ x , w ] &gt; d i s t ( v , y ) + d i s t ( y , w ) = d i s t ( v , w ) dist(u,x) + dist(u,y,w) = dist[x,w] &gt; dist(v,y) + dist(y,w) = dist(v,w) dist(u,x)+dist(u,y,w)=dist[x,w]>dist(v,y)+dist(y,w)=dist(v,w), 那么说明那么v-w不是树的是直径,跟假设矛盾。
      综上,方法二正确,且复杂度为2趟DFS,因此复杂度为 O ( n ) O(n) O(n)。比方法一快很多。在这里插入图片描述
      模板如下:
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    //maxv:源点能到的最远点,maxdis:最远点对应的距离, 
    const int maxn = 1e4 + 5;
    struct Edge { int to, next, w; }edges[2 * maxn];
    int head[maxn], maxdis,maxv, ne; 
    
    void add(int u, int v, int w) {
    	edges[ne] = { v, head[u], w };
    	head[u] = ne++;
    }
    
    //u:dfs的源点,f: u点的父节点,d2s:u点到源点的距离
    void dfs(int u, int f, int d2s) {
    	if (maxdis < d2s){
    		maxdis = d2s;
    		maxv = u;
    	}
    	for (int e = head[u]; e != -1; e = edges[e].next) {
    		int v = edges[e].to, w = edges[e].w;
    		if (v == f) continue;  //父节点已经访问过,防止重复遍历,相反孩子不会重复遍历。
    		dfs(v, u, d2s + w);
    	}
    }
    
    int main() {
    	int e, u, v, w, s;
    	cin >> e;
    	memset(head, -1, sizeof(head));
    	for (int i = 1; i <= e; i++) {
    		cin >> u >> v >> w;
    		add(u, v, w), add(v, u, w);
    	}
    	dfs(1, -1, 0); //从结点1开始遍历,找到最远点maxv及对应的最远距离maxdis
    	maxdis = 0;
    	dfs(maxv, -1, 0);//从结点maxv开始遍历,找到最远点对应的距离maxdis
    	cout << maxdis << endl;
    	return 0;
    }
    

    重要性质:
    树上任意点能到的最远点,一定是树的直径的某个端点。通过方法二的反证法可以推出此结论。
    例题:HDOJ 2196:http://acm.hdu.edu.cn/showproblem.php?pid=2196
    解法一:根据上述结论,先求出树的直径,然后从直径的两个端点u和v分别DFS整棵树,对于每个结点得到两个距离d[i].u和d[i].v, 二者的最大值即是i点能到的最远点的距离。

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1e4 + 5;
    struct Edge { int to, next, w; }edges[2 * maxn];
    int head[maxn], vis[maxn], d1[maxn], d2[maxn], maxv, n, ne;
    
    void add(int u, int v, int w) {
    	edges[ne] = { v, head[u], w };
    	head[u] = ne++;
    }
    
    void dfs(int u, int f, int depth, int* d) {
    	d[u] = depth;
    	if (d[maxv] < d[u]) maxv = u;
    	for (int e = head[u]; e != -1; e = edges[e].next) {
    		int v = edges[e].to, w = edges[e].w;
    		if (v == f) continue;
    		dfs(v, u, depth + w, d);
    	}
    }
    
    int main() {
    	int n, u, v, w, s;
    	while (~scanf("%d", &n)) {
    		memset(head, -1, sizeof(head));
    		ne = 0;
    		for (int i = 2; i <= n; i++) {
    			scanf("%d%d", &v, &w);
    			add(i, v, w), add(v, i, w);
    		}
    		s = 1, d1[maxv] = 0;
    		dfs(s, -1, 0, d1);
    		s = maxv, d1[maxv] = 0;
    		dfs(s, -1, 0, d1);
    		s = maxv, d2[maxv] = 0;
    		dfs(s, -1, 0, d2);
    
    		for (int i = 1; i <= n; i++)
    			printf("%d\n", max(d1[i], d2[i]));
    	}
    	return 0;
    }
    

    解法二:树上DP,讲解参见:
    1)https://www.cnblogs.com/WABoss/p/5267488.html?tdsourcetag=s_pcqq_aiomsg
    2)https://blog.csdn.net/shuangde800/article/details/9732825

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1e4 + 5;
    struct Edge { int to, next, w; }edges[2 * maxn];
    int head[maxn], dis[maxn][3], maxson[maxn], vis[maxn], n, tot;
    
    void add(int u, int v, int w) {
        edges[tot] = { v, head[u], w };
        head[u] = tot++;
    }
    void dfs1(int u) {
        vis[u] = 1; dis[u][0] = dis[u][1] = 0;
        for (int e = head[u]; e != -1; e = edges[e].next) {
            int v = edges[e].to, w = edges[e].w;
            if (vis[v]) continue;
            dfs1(v);
            int dist = dis[v][0] + w;
            if (dist >= dis[u][0]) {
                dis[u][1] = dis[u][0]; dis[u][0] = dist;
                maxson[u] = v;
            }
            else if (dist > dis[u][1]) 
                dis[u][1] = dist;
        }
    }
    void dfs2(int u) {
        vis[u] = 1;
        for (int e = head[u]; e != -1; e = edges[e].next) {
            int v = edges[e].to, w = edges[e].w;
            if (vis[v]) continue;
            if (v != maxson[u]) dis[v][2] = max(dis[u][0], dis[u][2]) + w;
            else  dis[v][2] = max(dis[u][1], dis[u][2]) + w;
            dfs2(v);
        }
    }
    
    void init() {
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        memset(maxson, 0, sizeof(maxson));
        tot = 0;
    }
    
    int main() {
        int u, v, w;
        while (~scanf("%d", &n)) {
            init();
            for (int i = 2; i <= n; i++) {
                scanf("%d%d", &v, &w);
                add(i, v, w);
                add(v, i, w);
            }
            dfs1(1);
            memset(vis, 0, sizeof(vis));
            dfs2(1);
            for (int i = 1; i <= n; i++)
                printf("%d\n", max(dis[i][0], dis[i][2]));
        }
        return 0;
    }
    
    展开全文
  • 在一个n各节点,n-1条无向边的无向图中,求图中最远两节点的距离,将这个图看作无根树,求的是树直径 树形dp求树的直径 我们不妨设1号点为根节点,那么这就可以看做一棵有根树。设D[x]表示从节点x出发,往以x为根的...

    在一个n各节点,n-1条无向边的无向图中,求图中最远两节点的距离,将这个图看作无根树,求的是树直径

    树形dp求树的直径
    我们不妨设1号点为根节点,那么这就可以看做一棵有根树。
    设D[x]表示从节点x出发,往以x为根的子树走,能够到达的最远距离。

    设x的子节点分别为y1,y2,y3,...,yt,edge(x,y)表示从x到y的边权,则可以得到状态转移方程:

        D[x]=max{D[yi]+edge(x,yi)}

    接下来,我们考虑对于每个节点x求出经过x的最长链的长度F[x],整棵树的直径就是max{F[x]}(1<=x<=n)。

    现在我们考虑如何求F[x]。
    对于任意两个节点yi和yj,经过节点x的最长链的长度可以通过四个部分来构成:

    • D[yi]
    • D[yj]
    • 从x到yi的距离
    • 从x到yj的距离

    不妨设j<i,则有:

     F[x]= max{D[yi]+D[yj]+edge(x,yi)+edge(x,yj)}
    void dp(int x){
      v[x]=1; 
      for(register int i=head[x];i;i=nxt[i]){
          int y=ver[i];
          if(v[y])continue;   
          dp(y); 
          ans=max(ans,d[x]+d[y]+edge[i]);
          d[x]=max(d[x],d[y]+edge[i]);
      }
    }

    代码解释可以看图:

     

    题意 : 先判断一下图中是否有环,有就直接输出YES,否则在输出这个无环图中的最长链
    思路分析:判断一个图中是否有环,采用并查集即可,找树上的最长链,也就是树的直径,有两种方法,一种是用采用树形dp,那么树上最长的链就是当前结点最远和次远的儿子加起来的和。
       dp[x][0] 表示树上次远的距离是多少, dp[x][1]表示树上最远的距离是多少。
    代码示例:
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int maxn=1e5+5;
    int n,m;
    struct node{
    	int to,cost;
    	node(int to,int cost){
    		this->to=to;
    		this->cost=cost;
    	}
    };
    vector<node>ve[maxn];
    int f[maxn];
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
    bool vis[maxn];
    int dp[maxn][2];
    int ans;
    void dfs(int x,int fa){
    	vis[x]=true;
    	for(int i=0;i<ve[x].size();i++){
    		int to=ve[x][i].to;
    		int cost=ve[x][i].cost;
    		
    		if(to==fa) continue;
    		dfs(to,x);
    		if (dp[x][1] < dp[to][1]+cost){
                dp[x][0] = dp[x][1];
                dp[x][1] = dp[to][1]+cost;
            }
            else if (dp[x][0] < dp[to][1]+cost)
                dp[x][0] = dp[to][1]+cost;    
        }  
       ans = max(ans, dp[x][1]+dp[x][0]);	
    }
    
    int main(){
    	int x,y,z;
    	 while(~scanf("%d%d", &n, &m)){
    		for(int i=1;i<=n;i++)f[i]=i,ve[i].clear();
    		int flag=0;
    		for(int i=1;i<=m;i++){
    			scanf("%d%d%d",&x,&y,&z);
    			ve[x].push_back(node(y,z));
    			ve[y].push_back(node(x,z));
    			int x1=find(x);int x2=find(y);
    			
    			if(x1==x2)flag=1;
    			else f[x1]=x2;
    		}
    		if (flag) {printf("YES\n"); continue;}
    		memset(vis,false,sizeof(vis));
    		memset(dp,0,sizeof(dp));
    		ans=0;
    		for(int i=1;i<=n;i++)//跑树dp 
    		    if(!vis[i]) dfs(i,0); //因为不成环,是很多个各不联通的分量,所以跑一遍循环
    		
    		printf("%d\n", ans);
    	}
    	return 0;
    }
    

     

    展开全文
  • 题解:首先我们树直径的合并,两颗子树合并后,新的树直径端点在原理两颗子树的树直径端点产生。那么我们就要查询任意树上两点之间的边权,需要一颗边权线段树,然后维护一颗树直径线段树。 注意:qu_path()函数中,...
  • 树形dp求树直径、两次dfs求树直径

    千次阅读 2018-12-10 22:37:00
    树形dp求树直径: #include<bits/stdc++.h> #include<ctime> #define ll long long using namespace std; const int N=100010,M=1000010; int head[N]; int ver[M]; int edge[M]; int Next[M]; bool v...
  • 直径两种求法

    2021-07-26 08:54:52
    首先先介绍一下什么是直径直径就是中所有最短路经距离的最大值。 求直径通常有两种方法,一种是通过两次搜索(bfs和dfs均可),另一种就是通过形dp来求了。 先来介绍一下用两次深搜来求的...
  • 对于一棵,每次询问删掉两棵子树的直径 每次删掉两颗子树相当于在dfsdfsdfs序挖掉两段区间再求解 我们在dfsdfsdfs序上维护一段区间内点集的直径 每次询问的时候考虑合并 有这么一个结论 合并两个相邻联通块...
  • 树直径模板 用到了vectpr中捆绑pair : https://blog.csdn.net/computer055maxi/article/details/6129736 #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;queue&gt;...
  • 直径详解

    千次阅读 2019-10-02 13:04:28
    直径,又称的最长链,定义为一棵上最远的两个节点的路径,即上一条不重复经过某一条边的最长的路径。直径也可以代指这条路径的长度。 求直径有两种比较常用的方法:形DP和搜索,时间复杂度均为...
  • 直径的概念

    2021-08-17 10:41:01
    直径的定义: 在一棵中,每一条边都有权值,中的两个点之间的距离,定义为连接两点的路径上边权之和, 那么上最远的两个点,他们之间的距离,就被称之为,直径直径的别称,的最长链。 请注意...
  • 题意:给一个,可能直径不唯一,求所有直径上的所有的点 思路:先用dp求直径,然后枚举每个直径中点,根据转移方程从中点dfs,把所有符合条件的点丢进set里面即可。 #include<iostream> #include<...
  • 动态维护直径

    2019-10-10 09:52:10
    打2019ICPC上海网络赛的时候,碰到了一道题(A),可以转化成动态维护直径的模型。但是由于不会写,就想要学习该算法,发现方法还多,一点一点学把。 首先是例题:https://nanti.jisuanke.com/t/41398 方法一:...
  • 树直径和树重心

    2019-10-31 15:15:30
    丛树的任一点开始找一个离该节点最远的点,该点必为树直径的一端点,再从该点出发找最远点即为树直径 方法:dfs 时间O(2n) 树重心 以某个节点为树根,最大子树最小的节点 方法是树dp 时间O(n) 要注意的...
  • 的重心和直径

    2019-05-30 16:54:25
    的重心 表达原理的代码 #include "bits/stdc++.h" using namespace std; const int maxn = 20000; const int INF = 2e9; int N; vector<int> tree[maxn+5]; int d[maxn+5]; int minNode; ...
  • 的中点和直径

    2019-09-03 19:13:45
    学习链接 这个 指的是 一个图 ,有n个点 n-1条边...的中点和直径 #include<bits/stdc++.h> using namespace std; #define Max 100050 int head[Max],Next[Max*2],ver[Max*2]; int tot; void add(int ...
  • 如何求直径

    2019-09-26 18:36:06
    直径给定一棵中每条边都有一个权值,中两点之间的距离定义为连接两点的路径边权之和。中最远的两个节点之间的距离被称为直径,连接这两点的路径被称为的最长链。后者通常也可称为直径,即直径是...
  •  直径上距离最远的两点间的距离,它在上问题上有许多应用,往往通过直径的性质可以将一个高时间复杂度的解法变为线性求解。对于上两点间距离通常有三种定义,我们根据这三种情况分别讨论一下它的...
  • 直径+证明

    2020-01-23 16:36:02
    直径:2点距离最远的路径。 结论 先说结论,对于一颗无根,首先随便找一个点 u 开始进行搜索,找到离当前点最远的一点 s , 然后从 s 开始搜最远的点 t ,直径就为 s - t 。 证明 找到直径,我们只需找到...
  • 基础算法 - 直径

    2020-10-15 16:54:10
    1245. 直径 难度中等48收藏分享切换为英文接收动态反馈 给你这棵「无向」,请你测算并返回它的「直径」:这棵上最长简单路径的边数。 我们用一个由所有「边」组成的数组edges来表示一棵无向,其中edges...
  • 直径及一点性质

    2020-08-13 22:06:08
    直径及一点性质定义求法上DP两遍dfs小性质&证明性质&证明 定义 中最长的简单路径,可能有多个。很多时候也指这个路径的长度。 求法 上DP 两遍dfsdfsdfs瞎搞一通,第一遍求出每个节点向下走到儿子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,990
精华内容 6,396
关键字:

树的直径