目录
1、距离和
2、流
3、最长路径
1、距离和
// // 距离和 #includeusing namespace std; const int N = 100005; #define ll long long ll n,f[N],v[N],size[N]; // 以 i 为根节点时，i的子节点到i的路径之和 int head[N]; struct edge{ int to,next; }e[N<<1]; int cnt = 0; bool vis[N]; inline void up(int i){ size[i] = 1; vis[i] = 1; for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; if(!vis[to]){ up(to); size[i] += size[to]; f[i] += f[to]; } } f[i] += size[i] -1; } inline void down(int i){ vis[i] = 1; for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; if(!vis[to]){// f[i] + v[i] : 以 i 为根节点的路径和 ！！！！！ v[to] = v[i] + f[i] - f[to] - size[to] + n - size[to]; down(to); // 求子v[]时，需要用到父v[],所以是先计算，再递归调用down } } } inline void makelist(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int main(){ memset(head,0,sizeof(head)); cin>>n; for(int i = 1; i < n; ++i){ int u,v;cin>>u>>v; makelist(u,v); makelist(v,u); } memset(vis,0,sizeof(vis)); up(1); // 求出f[i] 和 size[i] memset(vis,0,sizeof(vis)); down(1); // 求v[i] for(int i = 1; i <= n; ++i){ printf("%lldn", f[i] + v[i]); // f[i] : 以 i 为根节点，其子节点到根节点的路径和 （注意：这里没有换根，换根只是一种思想） // v[i] : i节点的父节点x作为i的子节点时，x节点那一部分对i节点的路径贡献 } return 0; }
2、流
// // 距离和 #includeusing namespace std; const int N = 100005; #define ll long long ll n,f[N],v[N]; // 以 i 为根节点时，i的子节点到i的路径之和 int head[N]; struct edge{ int to,w,next; }e[N<<1]; // f[j] : 以j为根节点的子树的消化能力 w ： 管道的流量限制 int cnt = 0; bool vis[N]; inline void up(int i){ vis[i] = 1; bool sign = 1; // 是否是叶子节点 for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; int w = e[x].w; if(!vis[to]){ up(to); f[i] += min(1ll * w,f[to]); sign = 0; } } if(sign)f[i] = 1<<30; } inline void down(int i){ vis[i] = 1; for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; int w = e[x].w; if(!vis[to]){ if(v[i] + f[i] == min(1ll*w,f[to])) // i是叶子节点 v[to] = w; else v[to] = min(f[i] + v[i] - min(1ll*w,f[to]),1ll*w); down(to); // 求子v[]时，需要用到父v[],所以是先计算，再递归调用down } } } inline void makelist(int u,int v,int w){ e[++cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt; } int main(){ memset(head,0,sizeof(head)); cin>>n; for(int i = 1; i < n; ++i){ int u,v,w;scanf("%d%d%d",&u,&v,&w); makelist(u,v,w); makelist(v,u,w); } memset(vis,0,sizeof(vis)); up(1); // 求出f[i] 和 size[i] memset(vis,0,sizeof(vis)); down(1); for(int i = 1; i <= n; ++i){ if(f[i]!=1<<30) printf("%lldn", f[i] + v[i]); else printf("%lldn", v[i]); } return 0; }
3、最长路径
// // 距离和 无根数 选根 #includeusing namespace std; const int N = 100005; #define ll long long int f[N][2][2],v[N]; // f[N][2][2] N : 每个节点； 二维0：最长 1：次长 ； 三维0：路径长度 1：从哪个点上来的。 int head[N]; struct edge{ int to,next; }e[N<<1]; int cnt = 0; int n; bool vis[N]; inline void up(int i){ vis[i] = 1; for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; if(!vis[to]){ up(to); if(f[to][0][0] + 1 > f[i][0][0]) f[i][1][0] = f[i][0][0], f[i][1][1] = f[i][0][1], f[i][0][0] = f[to][0][0] + 1, f[i][0][1] = to; else if(f[to][0][0] + 1 > f[i][1][0]) f[i][1][0] = f[to][0][0] + 1, f[i][1][1] = to; } } } inline void down(int i){ vis[i] = 1; for(int x = head[i]; x ; x = e[x].next){ int to = e[x].to; if(!vis[to]){ if(f[i][0][1] == to) v[to] = max(v[i],f[i][1][0]) + 1; else v[to] = max(f[i][0][0],v[i]) + 1; down(to); // 求子v[]时，需要用到父v[],所以是先计算，再递归调用down } } } inline void makelist(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int main(){ memset(head,0,sizeof(head)); cin>>n; for(int i = 1; i < n; ++i){ int u,v;cin>>u>>v; makelist(u,v); makelist(v,u); } memset(vis,0,sizeof(vis)); up(1); // 求出f[i] 和 size[i] memset(vis,0,sizeof(vis)); down(1); for(int i = 1; i <= n; ++i){ printf("%dn", f[i][0][0] + f[i][1][0] + v[i] - min(min(f[i][0][0],f[i][1][0]),v[i])); } return 0; }
