- 月赛
- 7 年前 @
2
36 条评论
-
lemonoil LV 9 @ 7 年前
我又回来了!!@@!!
-
7 年前@
那你自己看看代码%%%%%%
-
7 年前@
马上 我又被拉出去了
-
7 年前@
其实是一个道理,f[i][j]也是这样啊
-
7 年前@
所以要两个dfs 接下来就是f【i】【j】有什么用对吧
-
7 年前@
所以先得到自己儿子的所有F[i]值,再得到自己上面的F[i]值,这两者没办法同时进行
-
7 年前@
因为此时u的上面的点的F[i]都是0,没办法用上面更新下面
-
7 年前@
那么对于你要更新F[i],最简单也是必要的就是先统计自己son的F[j]
-
7 年前@
打个比方,对于以u为根来说,一共有三部分组成,一个是u,一个是u的上面,一个就是u的son组成的集合
-
7 年前@
即记录时自己的儿子的值应该先返回给自己,因为,必须知道所有的小辈部分的F[i]才能去为小辈更新他们的f[i][j]
-
7 年前@
不是很好讲,因为dfs1与dfs2的关系不是并列的
-
7 年前@
这里的方法就有点生涩了、、
-
7 年前@
这两者先后看似没有顺序,但是如果放在一起处理就会出事故、
-
7 年前@
只处理fa到i的情况肯定不行,只处理i到fa的情况也不行
-
7 年前@
回顾本题,这道题中指的是任意道路
-
7 年前@
与刚刚的先处理儿子在处理fa相反,所以这一次先处理fa在处理儿子
-
7 年前@
寓意就是fa[i]处理完了在来处理i
-
7 年前@
这次的dfs在处理下方
-
7 年前@
-
7 年前@
所以要第二次dfs
-
7 年前@
之后就是这样做完了为什么还要一次dfs对吧
-
7 年前@
我有一个疑惑的地方,因为第一次我是用dfs(1, 0),把1作为根来去遍历它的儿子,然后用儿子更新根,好像并没有把根的值去更新儿子?
-
7 年前@
公式原因我就不讲了。。
-
7 年前@
我们用它儿子的值即F[i(v)]去更新它的值F[fai],公式就是,F[x]+=F[v]+len(就是x与v的边长)/M(mod)
-
7 年前@
x为当前点,v为它的儿子,
-
7 年前@
对于i的father fa[i],来说,他的每一个儿子都可以对他本身的值产生贡献,所以这一次dfs为的是
cpp
F[x]+=F[v]+e[i].len/M;
f[x][e[i].len%M]++;
for(j=0;j<M;j++){
k=j+e[i].len;
F[x]+=k/M*f[v][j];
f[x][k%M]+=f[v][j];
}
-
7 年前@
或者这么说:f[i][j]可以对f[fa[i]][(j+len)/mod]+f[fa[i]][(j+len)%len]产生贡献
-
7 年前@
然后f[i][j]可以拆成f[i][(j+len)/mod]+f[i][(j+len)%len].
-
7 年前@
刚刚有事不好意思
-
7 年前@
求出了f[i][(j+len)%mod]
-
7 年前@
因为我们一开始定义的是这样:F[i]表示以i为根的和,然后f[i][j]就比较奇妙了,
-
7 年前@
接着 dfs1是计算f[i][(j+len)%mod]的值
-
7 年前@
我们考虑暴力计算mod的情况,因为mod很小,可以直接枚举。
-
7 年前@
是这样的
-
7 年前@
@????
好吧 @A 恩知道没用还是搞搞 -
7 年前@
dis(u, v)是题目中给的len吗
- 1