bzoj1060 luogu1131 [ZJOI2007]时态同步

朱雀 2021-10-18 16:20 326阅读 0赞

[https://www.lydsy.com/JudgeOnline/problem.php?id=1060][https_www.lydsy.com_JudgeOnline_problem.php_id_1060]

要放假了，有点静不下心，悄悄水两题......

#include<bits/stdc++.h>
    using namespace std;
    const int N=5*(1e5+5);
    int n,s;
    int head[N],ver[N<<1],nxt[N<<1],val[N<<1],ce;
    long long dep[N],ans;
    int rd()
    {
        char ch='!'; int res=0;
        while(ch<'0' || ch>'9') ch=getchar();
        while(ch>='0' && ch<='9') res=res*10+ch-'0',ch=getchar();
        return res;
    }
    void dfs(int now,int lst)
    {
        for(int i=head[now];i;i=nxt[i])
        {
            int y=ver[i];
            if(y==lst) continue;
            dfs(y,now);
            dep[now]=max(dep[y]+val[i],dep[now]);
        }
        for(int i=head[now];i;i=nxt[i])
        {
            int y=ver[i];
            if(y==lst) continue;
            ans+=dep[now]-dep[y]-val[i];
        }
    }
    void adde(int a,int b,int c)
    {
        ver[++ce]=b,val[ce]=c,nxt[ce]=head[a],head[a]=ce;
    }
    int main()
    {
        n=rd(),s=rd();
        for(int i=1;i<n;++i)
        {
            int u,v,w;
            u=rd(),v=rd(),w=rd();
            adde(u,v,w); adde(v,u,w);
        }
        dfs(s,0);
        printf("%lld",ans);
    }

转载于:https://www.cnblogs.com/w19567/p/11321359.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_1060]: https://www.lydsy.com/JudgeOnline/problem.php?id=1060

发表评论取消回复

表情：

评论列表（有 0 条评论，326人围观）

还没有评论，来说两句吧...

相关阅读

相关题解 Luogu P1110 【[ZJOI2007]报表统计】

感谢 @[cmy962085349][] 提供的hack数据，已经改对了。 -------------------- 先声明，我好像是题解里写双$fhq$ $treap$里

阳光穿透心脏的1/2处/ 2023年06月01日 12:42/ 0 赞/ 43 阅读

相关 P1169-[ZJOI2007]棋盘制作

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

太过爱你忘了你带给我的痛/ 2023年06月01日 08:53/ 0 赞/ 69 阅读

相关题解[ZJOI2007]矩阵游戏

详谈二分图最大匹配解法和网络流 Dinic解法 1.题目分析 2.匈牙利二分图匹配解法 3.Dinic网络流解法 -----------------

Love The Way You Lie/ 2021年12月22日 05:49/ 0 赞/ 270 阅读

相关【ZJOI2007】棋盘制作

Description 给定一个01矩阵，求出最大的正方形子矩阵和最大长方形子矩阵，并保证取出的矩阵中的元素都为0/1 Solution 为了使题目变成上述表述的

痛定思痛。/ 2021年12月12日 09:09/ 0 赞/ 277 阅读

相关【luogu2272】 [ZJOI2007]最大半连通子图 [tarjan 缩点][拓扑排序]

[P2272 \[ZJOI2007\]最大半连通子图][P2272_ _ZJOI2007] 首先缩点缩完点后存在大量重边排一遍序去重然后重新建一个新图再从入度为0的

深藏阁楼爱情的钟/ 2021年11月17日 15:44/ 0 赞/ 242 阅读

相关 bzoj4455 [Zjoi2016]小星星

题目描述： [bz][] [luogu][] 题解：大力容斥+卡常。考虑$dp\[i\]\[j\]$表示点$i$子树选完且点$i$对应点$j$的方案数，很好转移。

た入场券/ 2021年11月01日 09:38/ 0 赞/ 279 阅读

相关 BZOJ3527: [Zjoi2014]力

[传送门][Link 1] 首先显然 $E\[j\]=\\sum\_\{i=1\}^\{j-1\}\\frac\{q\[i\]\}\{(i-j)^2\}-\\sum\_\{i

小灰灰/ 2021年10月26日 12:00/ 0 赞/ 314 阅读

相关 bzoj1060 luogu1131 [ZJOI2007]时态同步

[https://www.lydsy.com/JudgeOnline/problem.php?id=1060][https_www.lydsy.com_JudgeOnline_

朱雀/ 2021年10月18日 16:20/ 0 赞/ 327 阅读

相关 bzoj1491 luogu2047 [NOI2007]社交网络

[https://www.lydsy.com/JudgeOnline/problem.php?id=1491][https_www.lydsy.com_JudgeOnline_

叁歲伎倆/ 2021年10月18日 16:20/ 0 赞/ 337 阅读

相关 BZOJ1059: [ZJOI2007]矩阵游戏

[BZOJ1059: \[ZJOI2007\]矩阵游戏][BZOJ1059_ _ZJOI2007] Description 小Q是一个非常聪明的孩子，除了国际象棋，他还

心已赠人/ 2021年09月30日 14:50/ 0 赞/ 321 阅读