COGS——T 2478. [HZOI 2016]简单的最近公共祖先

http://www.cogs.pro/cogs/problem/problem.php?pid=2478

★☆ 输入文件：easy_LCA.in 输出文件：easy_LCA.out 简单对比
时间限制：2 s 内存限制：128 MB

【题目描述】

给定一棵有n个节点的有根树，根节点为1，每个节点有一个权值

即求所有无序节点对的LCA的权值之和。

树的节点编号为1~n，LCA表示两节点的最近公共祖先，即在它们的所有公共祖先中离根节点最远的节点。

【输入格式】

第一行一个整数n，表示节点数。

第二行n个正整数，表示每个点的权值。

以下n-1行每行两个整数x,y，表示树上有一条边连接节点x和节点y。

【输出格式】

一个整数，表示答案。

【样例输入】

【样例输出】

【数据范围与约定】

对于30%的数据，n<=1000。

对于60%的数据，n<=100000。

对于100%的数据，1<=n<=1000000，0<

【来源】

HZOI 2016

数据范围暴力LCA只得30，所以、、

发现，一个点u与连出去的点v，两者的LCA是u，所以在DFS过程中

sum记录当前点遍历次数，统计答案时用当前用所有的次数*当前点权

最后加上本身与本身的情况

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 #define LL long long
 5 
 6 using namespace std;
 7  
 8 const int N(1000010);
 9 int n,w[N];
10  
11 int sumedge,head[N];
12 struct Edge
13 {
14     int from,to,next;
15     Edge(int from=0,int to=0,int next=0):from(from),to(to),next(next){}
16 }edge[N<<1];
17 inline void ins(int from,int to)
18 {
19     edge[++sumedge]=Edge(from,to,head[from]);
20     head[from]=sumedge;
21 }
22 
23 int dad[N];
24 LL ans,sum[N];
25 void DFS(int x)
26 {
27     sum[x]=1;
28     for(register int i=head[x];i;i=edge[i].next)
29     {
30         register int to=edge[i].to;
31         if(to!=dad[x])
32         {
33             dad[to]=x; DFS(to);
34             ans+=(LL)sum[x]*sum[to]*(LL)w[x];
35             sum[x]+=(LL)sum[to];
36         }
37     }
38 }
39 
40 inline void read(int &x)
41 {
42     x=0;register char ch=getchar();
43     for(;ch<'0'||ch>'9';) ch=getchar();
44     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
45 }
46 
47 int main()
48 {
49     freopen("easy_LCA.in","r",stdin);
50     freopen("easy_LCA.out","w",stdout);
51     read(n);
52     for(register int i=1;i<=n;i++) read(w[i]);
53     for(register int u,v,i=1;i<n;i++)
54         read(u),read(v),ins(u,v),ins(v,u);
55     DFS(1);
56     for(register int i=1;i<=n;i++) ans+=(LL)w[i];
57     printf("%lld",ans);
58     return 0;
59 }

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。