Codeforces 1189D2. Add on a Tree: Revolution
2024-10-01 03:49:47
首先可以证明一颗树合法的充分必要条件是不存在某个节点的度数为 $2$
首先它是必要的,考虑任意一条边连接的两点如果存在某一点 $x$ 度数为 $2$ ,那么说明 $x$ 还有连一条边出去,那么连出去的那一条边和当前边的权值就永远一样
然后它是充分的,考虑进行如下操作:首先设当前边连接的两端分别为 $L,R$ ,如果 $L,R$ 只要存在某一个度数为 $1$ 显然合法
然后考虑 $L,R$ 度数不为 $1$ 的情况,那么 $L,R$ 一定分别存在两个儿子连向叶子,设为 $Lx,Ly,Rx,Ry$
设当前边的目标权值为 $x$ ,那么只要操作: $(Lx,Rx,x/2),(Ly,Ry,x/2),(Lx,Ly,-x),(Rx,Ry,-x)$ 即可,由于 $x$ 为偶数,所以 $x/2$ 一定为整数
因为这一题可以 $n^2$ ,所以直接按上面描述模拟即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=1e5+;
int n,a[N],b[N],c[N],du[N];
int fir[N],from[N<<],to[N<<],cntt;
inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; }
int find(int x,int fa)
{
if(du[x]==) return x;
for(int i=fir[x];i;i=from[i])
if(to[i]!=fa) return find(to[i],x);
}
struct dat {
int x,y,z;
dat (int _x=,int _y=,int _z=) { x=_x,y=_y,z=_z; }
};
vector <dat> ans;
int main()
{
n=read();
for(int i=;i<n;i++)
{
a[i]=read(),b[i]=read(); c[i]=read();
add(a[i],b[i]); add(b[i],a[i]);
du[a[i]]++,du[b[i]]++;
}
if(n==) { printf("YES\n1\n1 2 %d\n",c[]); return ; }
for(int i=;i<n;i++)
{
if(du[a[i]]==||du[b[i]]==) { printf("NO\n"); return ; }
if(du[b[i]]==) swap(a[i],b[i]);
vector <int> L,R;
for(int j=fir[a[i]];j;j=from[j])
if(to[j]!=b[i]) L.push_back(find(to[j],a[i]));
for(int j=fir[b[i]];j;j=from[j])
if(to[j]!=a[i]) R.push_back(find(to[j],b[i]));
if(L.size()==)
ans.push_back(dat(a[i],R[],c[i]/)),
ans.push_back(dat(a[i],R[],c[i]/)),
ans.push_back(dat(R[],R[],-c[i]/));
else
ans.push_back(dat(L[],R[],c[i]/)),
ans.push_back(dat(L[],R[],c[i]/)),
ans.push_back(dat(L[],L[],-c[i]/)),
ans.push_back(dat(R[],R[],-c[i]/));
}
printf("YES\n%d\n",int(ans.size()));
for(auto A: ans) printf("%d %d %d\n",A.x,A.y,A.z);
return ;
}
最新文章
- 如何编写稳定流畅的iOS移动端应用
- Common Issues Which Cause Roles to Recycle
- js改变HTML元素的值
- centos6.5上安装Openfire 4.0.3
- webrtc 的回声抵消(aec、aecm)算法简介(转)
- Android的自动对焦
- iOS控件——UIView与UIImageView播放动画的实现方法
- 【转自CSDN】深入 Microsoft.VisualBasic.Strings.StrConv 簡繁轉換
- 深入理解C指针之六:指针和结构体
- Oracle 11g RAC 修改各类IP地址
- nagios与zabbix对比
- Spring源码情操陶冶-PathMatchingResourcePatternResolver路径资源匹配溶解器
- 前端性能优化 —— 添加Expires头与Cache-control区别
- 译:SOS_SCHEDULER_YIELD类型等待在虚拟机环境中的增多
- Log4J Appender - 将Log4J的日志内容发送到agent的source
- 微软BI 之SSRS 系列 - 基于时间段参数的 MDX 查询以及时间日历 Date Picker 的时间类型参数化
- DUAL PORT RAM应用实例
- Selenium模拟浏览器抓取淘宝美食信息
- makefile特殊符号介绍
- Odoo中的向导
热门文章
- JavaScript设计模式—代理模式
- [Javascript]客户端检测
- legend3---9、项目的日志以及调试信息数据量非常大
- mysql:启动服务时遇到的问题
- storm java.io.NotSerializableException
- eclipse syso 自动补全设置方法
- 一个Action中,可以写多个类似的业务控制方法
- C# WinForm设置窗口大小不可调,取消最大、最小化按键
- 小D课堂 - 新版本微服务springcloud+Docker教程_4-06 Feign核心源码解读和服务调用方式ribbon和Feign选择
- curl指令的坑