局域网站建设基本流程,seo最强,wordpress倒入数据库,中国建设业管理协会网站题意#xff1a;给你一颗树#xff0c;树的边权都是偶数#xff0c;并且边权各不相同。你可以选择树的两个叶子结点#xff0c;并且把两个叶子结点之间的路径加上一个值#xff08;可以为负数#xff09;#xff0c;问是否可以通过这种操作构造出这颗树#xff1f;如果…题意给你一颗树树的边权都是偶数并且边权各不相同。你可以选择树的两个叶子结点并且把两个叶子结点之间的路径加上一个值可以为负数问是否可以通过这种操作构造出这颗树如果可以输出构造方案。初始树的边权都是0。 思路A1很简单只要判断是否有度数为2的点就可以了。对于A2, 由于边权各不相同所以A1的结论同样适用。现在我们来构造一组答案。官方题解的构造方式是这样的我们假设要让一个节点u到叶子结点v的路径都加上一个值x并且知道叶子结点l1, l2都可以到达u我们执行以下操作v到l1的路径加上x / 2, v到l2的路径加上x / 2, l1 到 l2的路径加上-x / 2,这样除了u到v的路径其它路径的值没有变太菜了想不到。。。。那么我们从树根开始从上到下逐个构造边权即可。 由于n只有1000所以实现方式有两种。 第一种很暴力赋值操作直接暴力加复杂度O(n ^ 2)。 代码 #include bits/stdc.h
#define pii pairint, int
#define LL long long
using namespace std;
const int maxn 1010;
vectorpii G[maxn];
vectorint son[maxn];
LL add[maxn];
struct node {int x, y;LL z;
};
vectornode ans;
int root 1;
int f[maxn];
void adde(int x, int y, int z) {G[x].push_back(make_pair(y, z));G[y].push_back(make_pair(x, z));
}int dfs(int x, int fa) {f[x] fa;for (auto y : G[x]) {if(y.first fa) continue;int tmp dfs(y.first, x);son[x].push_back(tmp);}if(G[x].size() 1) {return x;}return son[x][0];
}void update(int x, int p, int val) {while(x ! p) {add[x] val;x f[x];}
}
void dfs1(int x, int fa) {int cnt 0;if(x root) {int y G[x][0].first;if(G[y].size() 1) {ans.push_back((node){x, y, G[x][0].second});return;}LL tmp G[x][0].second;ans.push_back((node){son[y][0], root, tmp / 2});ans.push_back((node){son[y][1], root, tmp / 2});ans.push_back(node{son[y][0], son[y][1], -tmp / 2});dfs1(y, x);} else {for (auto y : G[x]) {if(y.first fa) continue;LL tmp y.second - add[y.first];int tmp1;if(cnt 0) tmp1 1;else tmp1 0;ans.push_back((node){son[x][cnt], root, tmp / 2});ans.push_back((node){son[x][cnt], son[x][tmp1], tmp / 2});ans.push_back(node{root, son[x][tmp1], -tmp / 2});update(son[x][cnt], x, tmp);dfs1(y.first, x);cnt;}}
}int main() {int n;int x, y, z;scanf(%d, n);for (int i 1; i n; i) {scanf(%d%d%d, x, y, z);adde(x, y, z);}for (int i 1; i n; i) {if(G[i].size() 2) {printf(NO\n);return 0;}}for (int i 1; i n; i) {if(G[i].size() 1) {root i;break;}}dfs(root, -1);dfs1(root, -1);printf(YES\n);printf(%d\n, ans.size());for (int i 0; i ans.size(); i) {printf(%d %d %lld\n, ans[i].x, ans[i].y, ans[i].z);}
}第二种用了类似树剖中重儿子的思想我们给一颗子树中决定一个优先级最高的叶子结点这样加的操作是这个叶子结点到它的祖先的路径上进行的其它的路径没有影响这样累加影响的时候如果这个叶子结点把前面的影响累加上否则不加。复杂度O(n)。 代码 #include bits/stdc.h
#define pii pairint, int
#define LL long long
using namespace std;
const int maxn 1010;
vectorpii G[maxn];
vectorint son[maxn];
LL add[maxn];
struct node {int x, y;LL z;
};
vectornode ans;
int root 1;
int v[maxn];
void adde(int x, int y, int z) {G[x].push_back(make_pair(y, z));G[y].push_back(make_pair(x, z));
}int dfs(int x, int fa) {for (auto y : G[x]) {if(y.first fa) continue;int tmp dfs(y.first, x);son[x].push_back(tmp);}if(G[x].size() 1) {v[x] x;return x;}v[x] son[x][0];return son[x][0];
}void dfs1(int x, int fa, int tot) {int cnt 0;if(x root) {int y G[x][0].first;if(G[y].size() 1) {ans.push_back((node){x, y, G[x][0].second});return;}LL tmp G[x][0].second;ans.push_back((node){son[y][0], root, tmp / 2});ans.push_back((node){son[y][1], root, tmp / 2});ans.push_back(node{son[y][0], son[y][1], -tmp / 2});dfs1(y, x, 0);} else {for (auto y : G[x]) {if(y.first fa) continue;LL tmp y.second;if(v[y.first] v[x]) tmp - tot;int tmp1;if(cnt 0) tmp1 1;else tmp1 0;ans.push_back((node){son[x][cnt], root, tmp / 2});ans.push_back((node){son[x][cnt], son[x][tmp1], tmp / 2});ans.push_back(node{root, son[x][tmp1], -tmp / 2});dfs1(y.first, x, y.second);cnt;}}
}int main() {int n;int x, y, z;scanf(%d, n);for (int i 1; i n; i) {scanf(%d%d%d, x, y, z);adde(x, y, z);}for (int i 1; i n; i) {if(G[i].size() 2) {printf(NO\n);return 0;}}for (int i 1; i n; i) {if(G[i].size() 1) {root i;break;}}dfs(root, -1);dfs1(root, -1, 0);printf(YES\n);printf(%d\n, ans.size());for (int i 0; i ans.size(); i) {printf(%d %d %lld\n, ans[i].x, ans[i].y, ans[i].z);}
}两份代码中为了实现方便都找了一个度为1的点为根。 转载于:https://www.cnblogs.com/pkgunboat/p/11145961.html
