#include <iostream>
#include <algorithm>
#include <vector>
const long long INF = 1e17;
int time;
int tin[500005], tout[500005], depth[500005];
int SparseTable[21][1000005], Log[1000005];
long long DistanceFromRoot[500005];
std::vector <std::pair <int, int> > Adj[500005];
void DFS(int node, int p = -1)
{
SparseTable[0][time] = node;
tin[node] = time;
time++;
for(auto x : Adj[node])
{
if(x.first == p)
{
continue;
}
DistanceFromRoot[x.first] = DistanceFromRoot[node] + x.second;
depth[x.first] = depth[node] + 1;
DFS(x.first, node);
SparseTable[0][time] = node;
time++;
}
tout[node] = time;
}
int lower(int u, int v)
{
return depth[u] < depth[v] ? u : v;
}
void BuildLCA()
{
Log[0] = -1;
for(int i = 1; i <= 1000000; i++)
{
Log[i] = Log[i >> 1] + 1;
}
for(int i = 1; i <= 20; i++)
{
for(int j = 0; j + (1 << i) < 1000000; j++)
{
SparseTable[i][j] = lower(SparseTable[i - 1][j], SparseTable[i - 1][j + (1 << (i - 1))]);
}
}
}
int LCA(int u, int v)
{
int l = std::min(tin[u], tin[v]), r = std::max(tin[u], tin[v]);
return lower(SparseTable[Log[r - l + 1]][l], SparseTable[Log[r - l + 1]][r - (1 << Log[r - l + 1]) + 1]);
}
long long Distance(int u, int v)
{
return DistanceFromRoot[u] + DistanceFromRoot[v] - 2 * DistanceFromRoot[LCA(u, v)];
}
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0; i < N - 1; i++)
{
Adj[A[i]].emplace_back(B[i], D[i]);
Adj[B[i]].emplace_back(A[i], D[i]);
}
DFS(0);
BuildLCA();
}
int stack[500005], top;
int color[500005];
long long dp[500005][2];
std::vector <int> VirtualAdj[500005];
long long Solve(int node, int p = -1)
{
long long ans = INF;
dp[node][0] = dp[node][1] = INF;
for(auto x : VirtualAdj[node])
{
if(x == p)
{
continue;
}
long long temp = Distance(x, node);
ans = std::min(ans, Solve(x, node));
if(dp[x][0] != INF)
{
dp[node][0] = std::min(dp[node][0], dp[x][0] + temp);
}
if(dp[x][1] != INF)
{
dp[node][1] = std::min(dp[node][1], dp[x][1] + temp);
}
}
if(color[node] == 1)
{
dp[node][0] = 0;
}
if(color[node] == 2)
{
dp[node][1] = 0;
}
ans = std::min(ans, dp[node][0] + dp[node][1]);
VirtualAdj[node].clear();
color[node] = 0;
return ans;
}
long long Query(int S, int X[], int T, int Y[])
{
std::vector <int> Vertex;
for(int i = 0; i < S; i++)
{
color[X[i]] = 1;
Vertex.push_back(X[i]);
}
for(int i = 0; i < T; i++)
{
if(color[Y[i]] == 1)
{
for(auto x : Vertex)
{
color[x] = 0;
}
return 0;
}
color[Y[i]] = 2;
Vertex.push_back(Y[i]);
}
std::sort(Vertex.begin(), Vertex.end(), [](int u, int v){
return tin[u] < tin[v];
});
top = 0;
stack[0] = 0;
for(auto x : Vertex)
{
if(x != 0)
{
int temp = LCA(x, stack[top]);
if(temp != stack[top])
{
while(tin[temp] < tin[stack[top - 1]])
{
VirtualAdj[stack[top - 1]].push_back(stack[top]);
VirtualAdj[stack[top]].push_back(stack[top - 1]);
top--;
}
if(tin[temp] > tin[stack[top - 1]])
{
VirtualAdj[temp].push_back(stack[top]);
VirtualAdj[stack[top]].push_back(temp);
stack[top] = temp;
}
else
{
VirtualAdj[stack[top]].push_back(temp);
VirtualAdj[temp].push_back(stack[top]);
top--;
}
}
top++;
stack[top] = x;
}
}
for(int i = 0; i + 1 <= top; i++)
{
VirtualAdj[stack[i]].push_back(stack[i + 1]);
VirtualAdj[stack[i + 1]].push_back(stack[i]);
}
return Solve(0);
}
Compilation message
factories.cpp:7:5: error: 'int time' redeclared as different kind of entity
7 | int time;
| ^~~~
In file included from /usr/include/pthread.h:24,
from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:35,
from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
from /usr/include/c++/9/ext/atomicity.h:35,
from /usr/include/c++/9/bits/ios_base.h:39,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/ostream:38,
from /usr/include/c++/9/iostream:39,
from factories.cpp:1:
/usr/include/time.h:75:15: note: previous declaration 'time_t time(time_t*)'
75 | extern time_t time (time_t *__timer) __THROW;
| ^~~~
factories.cpp: In function 'void DFS(int, int)':
factories.cpp:15:21: error: invalid types 'int [1000005][time_t(time_t*) noexcept {aka long int(long int*) noexcept}]' for array subscript
15 | SparseTable[0][time] = node;
| ^
factories.cpp:16:14: error: invalid conversion from 'time_t (*)(time_t*) noexcept' {aka 'long int (*)(long int*) noexcept'} to 'int' [-fpermissive]
16 | tin[node] = time;
| ^~~~
| |
| time_t (*)(time_t*) noexcept {aka long int (*)(long int*) noexcept}
factories.cpp:17:6: warning: ISO C++ forbids incrementing a pointer of type 'time_t (*)(time_t*) noexcept' {aka 'long int (*)(long int*) noexcept'} [-Wpointer-arith]
17 | time++;
| ^~
factories.cpp:17:6: error: lvalue required as increment operand
factories.cpp:27:22: error: invalid types 'int [1000005][time_t(time_t*) noexcept {aka long int(long int*) noexcept}]' for array subscript
27 | SparseTable[0][time] = node;
| ^
factories.cpp:28:7: warning: ISO C++ forbids incrementing a pointer of type 'time_t (*)(time_t*) noexcept' {aka 'long int (*)(long int*) noexcept'} [-Wpointer-arith]
28 | time++;
| ^~
factories.cpp:28:7: error: lvalue required as increment operand
factories.cpp:30:15: error: invalid conversion from 'time_t (*)(time_t*) noexcept' {aka 'long int (*)(long int*) noexcept'} to 'int' [-fpermissive]
30 | tout[node] = time;
| ^~~~
| |
| time_t (*)(time_t*) noexcept {aka long int (*)(long int*) noexcept}
