[ZJOI2007]时态同步

[Time Gate]

https://www.luogu.org/problem/P1131

【解题思路】

看输入数据，由于n个节点只有n-1条边，不难看出这是一棵树。我们可以反着思考，就是让所有叶子节点同时发出信号，然后这些信号同时到达根节点。于是我们可以自下而上的进行维护，使得每一节点所有子节点的信号同时到达该节点。

于是我们考虑如何维护。我们从根节点开始搜索，搜索到叶子节点，回溯的时候进行维护，先维护节点的所有子节点到该节点最大边权（边权为叶子节点到同时到达它所需要时间）。然后维护答案，答案为最大边权减去所有到子节点的边权。然后维护父节点的边权，父节点边权为该节点子节点的 最大边权+父节点到该节点的时间。然后就回溯，重复操作，到根节点为止。好难说清楚啊QWQ 看注释更明白一点

然后我们要注意一些细节：

1. 一定要双向加边，是无向图。
2. 既然是无向图，维护时不要把到父节点的边计算了。
3. 维护的顺序一定不能乱。
4. 答案要用long long 存。

    1 #include <bits/stdc++.h>
    2 #define MAXN 1000005
    3 using namespace std;
    4 struct Edge{int next,to,dis;} edge[MAXN];
    5 int n,s,a,b,t,maxn[MAXN],cnt,head[MAXN];  //maxn储存到子节点的最大边权
    6 long long ans;  //注意，答案要用long long 存
    7 
    8 void addedge(int from, int to, int dis)  
    9 {
   10     edge[++cnt].next=head[from];
   11     edge[cnt].to=to;
   12     edge[cnt].dis=dis;
   13     head[from]=cnt;
   14 }  //前向星加边
   15 
   16 void dfs(int x, int fa) //X为当前搜索节点，fa为x的父亲节点
   17 {
   18     for(int i=head[x]; i; i=edge[i].next)
   19         if(edge[i].to!=fa) dfs(edge[i].to, x);
   20     //这一句一定要最先，先搜索到底层，回溯时再进行后续处理（从下向上维护）
   21     for(int i=head[x]; i; i=edge[i].next)
   22         if(edge[i].to!=fa) maxn[x]=max(maxn[x], edge[i].dis);
   23     //维护到子节点的最大边权
   24     for(int i=head[x]; i; i=edge[i].next)
   25         if(edge[i].to!=fa) ans+=(maxn[x]-edge[i].dis);
   26     //维护答案
   27     for(int i=head[fa]; i; i=edge[i].next)
   28         if(edge[i].to==x) edge[i].dis+=maxn[x];
   29     //这一句不能漏，更新父节点到该节点的边权
   30 }//注意顺序不能乱
   31 
   32 int main()
   33 {
   34     scanf("%d%d",&n,&s);
   35     for(int i=1; i<=n-1; i++)
   36     {
   37         scanf("%d%d%d",&a,&b,&t);
   38         addedge(a, b, t);
   39         addedge(b, a, t); //是无向图，双向加边
   40     }
   41     dfs(s, 0);
   42     printf("%lld\n",ans);
   43     return 0;
   44 }

    

【code】

[ZJOI2007]时态同步

原文：https://www.cnblogs.com/66dzb/p/11243483.html