做自己网站彩票,wordpress子目录,福建省城乡建设信息网站,深圳制作网站的公司简介文章目录题目描述解析代码题目描述
给出一棵带边权的树#xff0c;求所有至少有一个端点为叶节点的所有简单路径的长度和
解析
换一个角度想 考虑将树分割为AB两部分的一条边会存在于多少条符合条件的路径中#xff08;也就是边权会考虑多少次#xff09; 不难发现#…
文章目录题目描述解析代码题目描述
给出一棵带边权的树求所有至少有一个端点为叶节点的所有简单路径的长度和
解析
换一个角度想 考虑将树分割为AB两部分的一条边会存在于多少条符合条件的路径中也就是边权会考虑多少次 不难发现这个次数就是A的叶节点个数与B节点数的乘积加上B的叶节点个数与A节点数的乘积 这样本题就迎刃而解了
这题提供了一种换角度看问题的思路 不考虑有多少条路径而是看每条边记录的次数 类似于逆向思维 2021省选《滚榜》用类似的逆向想法能很轻易的写出60分的暴力 这是一个很值得学习的思路
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
int m,n;
int jd[N],nm0;
struct node{int to,nxt;ll v;
}p[N];
int fi[N],tot-1,id[N];
void addline(int x,int y,int v){p[tot](node){y,fi[x],v};fi[x]tot;
}int ru[N];
ll tt,size[N],num[N];
void dfs(int x,int fa){size[x]1;if(ru[x]1) num[x]1,tt;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa) continue;dfs(to,x);size[x]size[to];num[x]num[to];}return;
}ll ans;
void find(int x,int fa){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tofa) continue;find(to,x);ans(ll)p[i].v*( num[to]*(n-size[to]) size[to]*(tt-num[to]) );}
}
int main(){memset(fi,-1,sizeof(fi));
// printf(%d,sizeof(fi)/1024/1024);scanf(%d%d,n,m);for(int i1;im;i){int a,b,c;scanf(%d%d%d,a,b,c);if(jd[c]0) id[nm]c,jd[c]1;if(jd[b]0) id[nm]b,jd[b]1;ru[b];ru[c];addline(b,c,a);addline(c,b,a);}dfs(id[1],0);find(id[1],0);printf(%lld,ans);
}
