Created
July 7, 2018 08:47
-
-
Save GoBigorGoHome/6cce55ac50ae23eb07bf323f82edb45e to your computer and use it in GitHub Desktop.
CF #1004E Sonya and Ice Cream part
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
#define pb push_back | |
#define eb emplace_back | |
#define all(x) x.begin(), x.end() | |
#define debug(x) cerr << #x <<": " << (x) << endl | |
//在每个函数的入口处执行一次,出口处执行一次。然后就可以快速得知是哪个地方段错误了 | |
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__) | |
#ifdef LOCAL | |
#define see(x) cout << #x << ": " << (x) << endl | |
#endif | |
#ifndef LOCAL | |
#define see(x) | |
#endif | |
#define RED "\033[31m" | |
#define RESET "\033[0m" | |
#define alert(x) cerr << RED << x << RESET << endl | |
#ifndef LOCAL | |
#define see(x) | |
#endif | |
#define rep(n) for(int _ = 0; _ != (n); ++_) | |
//#define rep(i, a, b) for(int i = (a); i <= (b); ++i) | |
#define Rng(i, n) for(int i = 0; i != (n); ++i) | |
#define rng(i, a, b) for(int i = (a); i != (b); ++i) | |
#define RNG(i, a) for(auto &i: (a)) | |
#define dwn(i, r, l) for(int i = (r); i>=(l); i--) | |
namespace std { | |
template<class T> | |
T begin(std::pair<T, T> p) | |
{ | |
return p.first; | |
} | |
template<class T> | |
T end(std::pair<T, T> p) | |
{ | |
return p.second; | |
} | |
} | |
#if __cplusplus < 201402L | |
template<class Iterator> | |
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it) | |
{ | |
return std::reverse_iterator<Iterator>(it); | |
} | |
#endif | |
template<class Range> | |
std::pair<std::reverse_iterator<decltype(begin(std::declval<Range>()))>, std::reverse_iterator<decltype(begin(std::declval<Range>()))>> make_reverse_range(Range &&r) | |
{ | |
return std::make_pair(make_reverse_iterator(::begin(r)), make_reverse_iterator(::end(r))); | |
} | |
#define RRNG(x, cont) for (auto &x: make_reverse_range(cont)) | |
template<class T> int sign(const T &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; } | |
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);} | |
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);} | |
template<class T> void Min(T &a, const T &b){ a = min(a, b); } | |
template<class T> void Max(T &a, const T &b){ a = max(a, b); } | |
template<typename T> void println(const T &t) { cout << t << '\n'; } | |
template<typename T, typename ...Args> void println(const T &t, const Args &...rest) { cout << t << ' '; println(rest...); } | |
template<typename T> void print(const T &t) { cout << t << ' '; } | |
template<typename T, typename ...Args> void print(const T &t, const Args &...rest) { cout << t; print(rest...); } | |
// this overload is chosen when there's only one argument | |
template<class T> void scan(T &t) { cin >> t; } | |
template<class T, class ...Args> void scan(T &a, Args &...rest) { cin >> a; scan(rest...); } | |
int cas; | |
const double pi = acos(-1); | |
int mod = 1e9 + 7; | |
template<class T> | |
void add_mod(T &a, const T &b) { | |
a += b; | |
if (a >= mod) a -= mod; | |
} | |
template<class T> | |
void sub_mod(T &a, const T &b){ | |
a -= b; | |
if (a < 0) a += mod; | |
} | |
auto bo=[](int x){ //二进制输出 | |
bitset<5> a(x); | |
cout << a << endl; | |
}; | |
using ll = long long; | |
using ull = unsigned long long; | |
using vec = vector<ll>; | |
using mat = vector<vec>; | |
using pii = pair<int, int>; | |
using pdd = pair<double, double>; | |
using pip = pair<int, pii>; | |
using szt = size_t; | |
using vi = vector<int>; | |
using vl = vector<ll>; | |
using vb = vector<bool>; | |
using vpii = vector<pii>; | |
using vvi = vector<vi>; | |
mat operator*(const mat &a, const mat &b) { | |
mat c(a.size(), vec(b[0].size())); | |
for (int i = 0; i < a.size(); i++) { | |
for (int j = 0; j < a[0].size(); j++) { | |
if (a[i][j]) { // optimization for sparse matrix | |
for (int k = 0; k < b[0].size(); k++) { | |
add_mod(c[i][k], a[i][j] * b[j][k] % mod); | |
} | |
} | |
} | |
} | |
return c; | |
} | |
vec operator*(const mat &a, const vec &b) { | |
vec c(a.size()); | |
for (int i = 0; i < a.size(); i++) { | |
for (int j = 0; j < a[0].size(); j++) { | |
add_mod(c[i], a[i][j] * b[j] % mod); | |
} | |
} | |
return c; | |
} | |
mat pow(mat a, ull n) { | |
mat res(a.size(), vec(a[0].size())); | |
for (int i = 0; i < a.size(); i++) { | |
res[i][i] = 1; | |
} | |
while (n) { | |
if (n & 1) { | |
res = res * a; | |
} | |
a = a * a; | |
n >>= 1; | |
} | |
return res; | |
} | |
ll POW(ll x, ll n) { | |
ll res = 1; | |
for (; n; n /= 2, x *= x, x %= mod) { | |
if (n & 1) { | |
res *= x; | |
res %= mod; | |
} | |
} | |
return res; | |
} | |
ll inv(ll x) { | |
return POW(x, mod - 2); | |
} | |
// 2D rotation | |
void rotate(double &x, double &y, double theta) { | |
double tx = cos(theta) * x - sin(theta) * y; | |
double ty = sin(theta) * x + cos(theta) * y; | |
x = tx, y = ty; | |
} | |
namespace bit { | |
const int BIT_N = 1e5 + 5; | |
int bit[BIT_N]; | |
int sum(int x) { | |
int res = 0; | |
while (x) { | |
res += bit[x]; | |
x -= x & -x; | |
} | |
return res; | |
} | |
int sum(int l, int r) { | |
if (l > r) return 0; | |
return sum(r) - sum(l - 1); | |
} | |
void add(int x, int v, int n) { | |
while (x <= n) { | |
bit[x] += v; | |
x += x & -x; | |
} | |
} | |
} | |
namespace util{ | |
int len(ll x){return snprintf(nullptr, 0, "%lld", x);} | |
vi get_d(ll x){ | |
vi res; | |
while(x) { | |
res.pb(x%10); | |
x /= 10; | |
} | |
reverse(all(res)); | |
return res; | |
} | |
template <class T> T parity(const T &a){ | |
return a & 1; | |
} | |
} | |
using namespace util; | |
// #include <ext/pb_ds/priority_queue.hpp> | |
// typedef __gnu_pbds :: priority_queue<pip, less<pip>, __gnu_pbds::thin_heap_tag > Heap; | |
// Heap h; | |
// Heap::point_iterator pos[N][N]; | |
const ll LINF = LLONG_MAX/10; | |
const int INF = INT_MAX/10; | |
const int M = 3000 + 5; | |
const int N = 1e5+5; | |
/* 问题:在一棵树中,从u出发所能走出的最长的简单路径的长度。 | |
* dp[0][u]:从u出发向下走所能走出的最长路的长度 | |
* dp[1][u]:从u出发向下走,进入与dp[0][u]不一样的子树所能走出的最长路的长度。 | |
* dp[1][u]:从u出发第一步向上走并且不再经过u,所能走出的最长路的长度。 | |
*/ | |
int dp[3][N]; | |
vpii g[N]; | |
int f[N]; // 记录父节点 | |
int d[N]; // 记录与父节点之间的边长 | |
void dfs(int u, int fa){ | |
f[u] = fa; | |
dp[0][u] = dp[1][u] = 0; | |
RNG(e, g[u]) { | |
int v = e.first, c = e.second; | |
if(v==fa) continue; | |
d[v] = c; | |
dfs(v, u); | |
if(dp[v][0]+c > dp[u][0]){ | |
dp[u][1] = dp[u][0]; | |
dp[u][0] = dp[v][0] + c; | |
} | |
else{ | |
Max(dp[u][1], dp[v][0] + c); | |
} | |
} | |
} | |
void dfs2(int u, int fa){ | |
RNG(e, g[u]) { | |
int v = e.first, c = e.second; | |
if (v == fa) continue; | |
dp[v][2] = 0; | |
if(dp[u][0]==dp[v][0] + c){ // 第二步向下走 | |
Max(dp[v][2], dp[u][1] + c); | |
} | |
else{ | |
Max(dp[v][2], dp[u][0] + c); | |
} | |
Max(dp[v][2], dp[u][2] + c); | |
dfs2(v, u); | |
} | |
} | |
int main() { | |
// Single Cut of Failure taut me | |
cout << std::fixed; // std::fixed 使得所有实数(默认)输出6位小数,即使实际小数位数多于6位。 | |
cout << setprecision(10); | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
#ifdef LOCAL | |
freopen("main.in", "r", stdin); | |
// freopen("main.out", "w", stdout); | |
#endif | |
int n, k; | |
scan(n, k); | |
rep(n-1) { | |
int u, v, c; | |
scan(u, v, c); | |
g[u].eb(v,c); | |
g[v].eb(u,c); | |
} | |
dfs(1, 1); | |
dp[1][2] = 0; | |
dfs2(1, 1); | |
auto check=[n](int x){ | |
vb used(n+1); | |
if(dp[1][0] <= x) return 1; | |
rng(i, 2, n+1){ | |
if(dp[0][i] <= x && dp[0][f[i]] > x){ // i和f[i]不可能同时满足此条件 | |
used[i] = true; | |
if(d[i] > x) used[f[i]] = true; | |
} | |
} | |
}; | |
rng(i, 1, n+1) { | |
if(dp[0][i]) | |
} | |
#ifdef LOCAL | |
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; | |
#endif | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment