企业网站打不开了,看守所加强自身网站建设工作,全球做的比较好的网站有哪些,简单项目计划书模板小明正在做一个网络实验。
他设置了 n n n 台电脑#xff0c;称为节点#xff0c;用于收发和存储数据。
初始时#xff0c;所有节点都是独立的#xff0c;不存在任何连接。
小明可以通过网线将两个节点连接起来#xff0c;连接后两个节点就可以互相通信了。
两个节点…小明正在做一个网络实验。
他设置了 n n n 台电脑称为节点用于收发和存储数据。
初始时所有节点都是独立的不存在任何连接。
小明可以通过网线将两个节点连接起来连接后两个节点就可以互相通信了。
两个节点如果存在网线连接称为相邻。
小明有时会测试当时的网络他会在某个节点发送一条信息信息会发送到每个相邻的节点之后这些节点又会转发到自己相邻的节点直到所有直接或间接相邻的节点都收到了信息。
所有发送和接收的节点都会将信息存储下来。
一条信息只存储一次。
给出小明连接和测试的过程请计算出每个节点存储信息的大小。
输入格式 输入的第一行包含两个整数 n,m分别表示节点数量和操作数量。
节点从 1 1 1 至 n n n 编号。
接下来 m m m 行每行三个整数表示一个操作。
如果操作为 1 a b表示将节点 a a a 和节点 b b b 通过网线连接起来。当 a b a b ab 时表示连接了一个自环对网络没有实质影响。 如果操作为 2 p t表示在节点 p p p 上发送一条大小为 t t t 的信息。
输出格式 输出一行包含 n n n 个整数相邻整数之间用一个空格分割依次表示进行完上述操作后节点 1 1 1 至节点 n n n 上存储信息的大小。
数据范围 1 ≤ n ≤ 10000 , 1≤n≤10000, 1≤n≤10000, 1 ≤ m ≤ 1 0 5 , 1≤m≤10^5, 1≤m≤105, 1 ≤ t ≤ 100 1≤t≤100 1≤t≤100
输入样例1
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1输出样例1
13 13 5 3本题做法参考至题解
单纯用并查集这道题是没有办法解决的因为不光需要合并集合同时也要求了查询某一点。 对于此可以使用树上差分。
可以在合并集合的过程中同时建立起多颗树这时候就可以保证信息量的加法仅加在集合中并且能过查询单点。
在增加信息量的操作时我们先给那些建立的根节点加上然后再最后遍历所有根节点让每棵树的值通过根节点一步步传递到叶节点最终打成连通增加信息量的效果。
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
const int M N 1;int h[N], e[M], ne[M], idx;
void add(int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx;
}
int n, m;
int p[N];
int cnt[N];int find(int x) {if (p[x] ! x)p[x] find(p[x]);return p[x];
}void dfs(int u, int f) {cnt[u] cnt[f];//cnt[u]:传入的节点的值//cnt[f]:传入的父节点的值可以观察到后面每一层传入的都是u都是根节点// //遍历树并且让每一颗树的子树节点都加上父节点存储的值for (int i h[u]; i ! -1; i ne[i]) {dfs(e[i], u);//搜下一层}
}int main() {memset(h, -1, sizeof h);cin n m;for (int i 1; i n * 2; i)p[i] i;int root n 1;while (m--) {int op, a, b; cin op a b;if (op 1) {a find(a), b find(b);//这里要提前把a和b的祖宗提取出来不然在下边建树的过程中会导致爆栈不知道为啥if (a ! b) {p[a] p[b] root;add(root, a);add(root, b);root;//之后来的点建树就要另换一颗树}}else {cnt[find(a)] b;//这里先只让祖宗节点加}}//扫所有的根节点for (int i n 1; i root; i)if (p[i] i) //如果这个根节点的祖先是自己也就是说他是最根部的根节点dfs(i, 0); //那就扫遍整个树并且使这棵树上所有的点加上自己的信息量然后再一层层传递到叶节点//这里需要加一层判断是因为上述过程中n1之后的节点也有可能被合并到其他的根节点上//传入i0,因为根节点自己不需要加i作为根节点传入for (int i 1; i n; i)cout cnt[i] ;return 0;
}
