bzoj1060 luogu1131 [ZJOI2007]时态同步

朱雀 2021-10-18 16:20 255阅读 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 条评论，255人围观）

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

相关阅读

相关洛谷 P1169 [ZJOI2007]棋盘制作

题意给定一个n\m的01矩阵，寻找最大的，相邻值不相同的子矩阵与子方阵。 \\(n,m\\leq 2,000\\) 分析朴素的做法是枚举两个点来确定矩阵，再

喜欢ヅ旅行/ 2023年08月17日 17:49/ 0 赞/ 98 阅读

相关 BZOJ1030 [JSOI2007] 文本生成器

我再看错模数我就是呆头考虑包含任意的补集不包含任何然后典型的AC自动机上dp 长度为l不能走到任何关键点特么模数多写了个0 问题是我刚跟zyf吐槽了模数就当考前

朱雀/ 2021年12月23日 06:19/ 0 赞/ 196 阅读

相关题解[ZJOI2007]矩阵游戏

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

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

相关【ZJOI2007】棋盘制作

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

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

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

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

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

相关 bzoj4455 [Zjoi2016]小星星

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

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

相关 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 赞/ 236 阅读

相关 bzoj1060 luogu1131 [ZJOI2007]时态同步

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

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

相关 bzoj1491 luogu2047 [NOI2007]社交网络

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

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

相关 BZOJ1059: [ZJOI2007]矩阵游戏

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

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