Pagini recente » Cod sursa (job #1253372) | Cod sursa (job #653558) | Cod sursa (job #1772936) | Cod sursa (job #1661192) | Cod sursa (job #2964175)
/// incomplet
/// scris la scoala pt problema xormax(ioit runda3)
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int NMAX = 5e4;
const int LOGMAX = 32;
int n, q;
vector <int> adj[NMAX + 1];
struct Edge{
int a, b, c;
}edges[NMAX + 1];
int level[NMAX + 1];
void dfs1(int nod, int parent){
level[nod] = level[parent] + 1;
for(int child : adj[nod]){
if(child != parent){
dfs1(child, nod);
}
}
}
int xor[NMAX + 1];
int cost[NMAX + 1];
void dfs2(int nod, int parent){
xor[nod] = cost[nod] ^ xor[parent];
for(int child : adj[nod]){
if(child != parent){
dfs2(child, nod);
}
}
}
struct Update{
int Start;
int End;
Update(){
Start = -1;
End = -1;
}
}updates[NMAX + 1];
namespace Trie{
struct Node{
Node *nxt[2];
Node(){
nxt[0] = NULL;
nxt[1] = NULL;
}
};
Node *root = new Node;
void Insert(Node *node, int x, int pos){
if(pos < 0){
return;
}
bool bit = ((x & (1 << pos)) > 0);
if(node->nxt[bit] == NULL){
node->nxt[bit] = new Node;
}
Insert(node->nxt[bit], x, pos - 1);
}
void Delete(Node *node, int x, int pos){
/// TODO: to implement this function!
}
int findXorMax(Node *node, int x, int pos){
if(pos < 0){
return 0;
}
bool targetBit = !((x & (1 << pos)) > 0);
if(node->nxt[targetBit] != NULL){
return targetBit * (1 << pos) + findXorMax(node->nxt[targetBit], x, pos - 1)
}
return !targetBit * (1 << pos) + findXorMax(node->nxt[!targetBit], x, pos - 1);
}
};
namespace AINT{
vector <int> aint[4 * NMAX + 1];
void update(int nod, int st, int dr, int uSt, int uDr, int val){
if(uSt <= st && dr <= uDr){
aint[nod].push_back(val);
return;
}
int mij = (st + dr) / 2;
if(uSt <= mij){
update(2 * nod, st, mij, uSt, uDr, val);
}
if(mij + 1 <= uDr){
update(2 * nod + 1, mij + 1, dr, uSt, uDr, val);
}
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n - 1; i++){
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back(b);
adj[b].push_back(a);
edges[i] = {a, b, c};
}
dfs1(1, 0);
for(int i = 1; i <= n - 1; i++){
if(level[edges[i].a] > level[edges[i].b]){
cost[edges[i].a] = edges[i].c;
}else{
cost[edges[i].b] = edges[i].c;
}
}
for(int i = 1; i <= q; i++){
int x;
cin >> x;
if(updates[x].Start == -1){
updates[x].Start = i;
}else{
updates[x].End = i;
}
}
for(int i = 1; i <= n; i++){
if(updates[i].Start != -1 && updates[i].End == -1){
updates[i].End = n + 1;
}
}
for(int i = 1; i <= n; i++){
if(updates[i].Start != -1){
AINT::update(1, 1, n + 1, updates[i].Start, updates[i].End, i);
}
}
return 0;
}