树是指由n个点，n-1条边构成的联通无向图。如果有一棵树，它的每一条边(u,v)都有一个权值l(u,v)，我们把这样的树称作带权树。我们知道对于树上的任意两个点，他们之间的路径是唯一的。对于两个点u，v来说，我们可以算出u与v之间的路径上的所有边权之和，将其称作u与v之间路径的长度，记作d(u,v)。你的任务是计算：∑d(u,v) (u!=v)【输入文件】输入文件的第一行为一个正整数n。接下来的n-1行，每行三个非负整数x，y，w表示点x与点y之间有一条权值为w的一条边。保证输入的图示一棵树。【输出文件】输出文件仅包含一行一个数，即答案。因为结果可能很大，请将答案模100 000 007输出【输入样例】41 2 41 3 41 4 4【输出样例】72【样例解释】d(1,2)+d(1,3)+d(1,4)=4+4+4=12d(2,1)+d(2,3)+d(2,4)=4+8+8=20d(3,1)+d(3,2)+d(3,4)=4+8+8=20d(4,1)+d(4,2)+d(4,3)=4+8+8=20ans=12+20+20+20=72【数据范围】n≤3×10^5 0≤w<1000000007
【分析】：
看n的范围肯定不能枚举……那么我们就换个角度，考虑每条边对答案的贡献！首先随便选一个点作根，dfs出每个子树的size大小与deep深度,那么可以发现对于deep[v]=deep[u]+1的两点，他们之间的边l(u,v)在答案中会被选size[v]*(n-size[v])次，枚举每条边看看即可。最优因为点对是无序的，但是我们只是算了从u那一边选v，所以我们还要×2算从v那一边选u。
#include#include #include #include #include #include #include #include #define ll long long#define N 1000001#define mod 100000007using namespace std;ll n,ans,root,cnt,first[N],size[N],depth[N];bool vis[N];struct edge{int next,from,to;ll len;}e[N];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}void add(int x,int y,int w){ e[++cnt].next=first[x]; e[cnt].from=x; e[cnt].to=y; e[cnt].len=w; first[x]=cnt;}void dfs(int now){ size[now]=1,vis[now]=true; for(int i=first[now];i;i=e[i].next) { int next=e[i].to; if(!vis[next]) { depth[next]=depth[now]+1; dfs(next); size[now]+=size[next]; } }}int main(){ int sizee = 50 << 20; //开50MB系统栈 char *p = (char*)malloc(sizee) + sizee; __asm__("movl %0, %%esp\n" :: "r"(p)); //freopen("tree1.in","r",stdin); //freopen("tree.out","w",stdout); n=read(); for(int i=1;i
概念
树的dfs遍历就是对于一个树上每个点 root，它向下的多个分支，选择一个分支一直走下去，直至走完并回溯到root再走其他分支形成的遍历。
Code
void dfs(int u,int fa){ vis[u]=1; //邻接表枚举i的每个相邻节点 for(int i=link[u]; i; i=e[i].next) { int v = e[i].u; if(v!=fa) dfs(v,u); }} 求树的深度
每个节点x的深度用deep[x]表示。 代码只要在dfs向下搜索前deep[e[i].y]=deep[x]+1;
求子树大小
以x节点为根节点的子树大小size[x]； 在dfs向下搜索之后size[x]+=size[e[i].y];
树的重心
对于一个节点x，如果把它从树中删除，原来的一棵树可能会分成若干个不相连的部分，每部分都是一颗子树。 设 Maxp(x)表示在删除节点x后分成的子树中，包含节点最多的那颗子树的节点数。 对于所有点来说，如果使得Maxp(x)最小的节点x就成为整颗树的重心。
int pos;//记录重心的编号void dfs(int x,int fa){ v[x]=1; sz[x]=1; int Maxp=0; //邻接表枚举i的每个相邻节点 for(int i=link[x]; i; i=e[i].next) { int y=e[i].y; if(y!=fa) { dfs(y,x); sz[x]+=sz[y]; Maxp=max(Maxp,sz[y]); } } Maxp=max(Maxp,n-sz[x]); if(Maxp 树的DFS序就是在对树进行DFS的时候，对树的节点进行重新编号；
DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们可以解决很多问题。void DFS(int u, int fa){ L[u] = ++dfs_clock; for(int k = head[u]; ~k; k = E[k].next) { int v = E[k].to; if(v == fa) continue; DFS(v, u); } R[u] = dfs_clock;}