Problem Code: PSHTTR Add problem to Todo list Submit Tweet

本文主要是介绍Problem Code: PSHTTR Add problem to Todo list Submit Tweet，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PSHTTR: Pishty 和城堡
题目描述
Pishty 是生活在胡斯特市的一个小男孩。胡斯特是胡克兰境内的一个古城，以其中世纪风格
的古堡和非常聪明的熊闻名全国。
胡斯特的镇城之宝是就是这么一座古堡，历史上胡斯特依靠这座古堡抵挡住了疯人国的大军。
对于 Pishty 来说，真正吸引他的是古堡悠长的走廊和高耸的钟楼，以及深藏于其中的秘密……
古堡可以用一棵 N 个节点的树的描述，树中有 N − 1 条无向边，每条边有一个魔法数字 C。
当一个旅游团参观古堡时，他们会选择树上 U 到 V 的路径游览。他们认为，如果一条边的魔
法数字不超过 K，那么这条边是有趣的。而一条路径的吸引力就是路径上所有有趣的边的魔法数
字的异或和。
胡克兰的国王希望大力发展旅游业，因此他下令求出所有旅游团的游览路径的吸引力。而
Pishty 立志成为国王身边的骑士，便自告奋勇承担了这一任务。但旅游团实在太多了，他也算不过
来。所以，请你帮 Pishty 解决这一问题：给定 M 个旅游团的旅游路径，请你求出路径的吸引力。
输入格式
输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含一个整数 N，代表树的节点个数。
接下来 N − 1 行，每行描述一条边。每行包含三个整数 U, V, C，代表节点 U 和 V 之间连有
一条魔法数字为 C 的边。
接下来一行包含一个整数 M，代表旅游团的数量。
接下来 M 行，每行包含三个整数 U, V, K，描述一个旅游团。
输出格式
对于每个旅游团，输出一行，包含一个整数，代表其路径的吸引力。
数据范围和子任务
• 1 ≤ T ≤ 5
• 1 ≤ N, M ≤ 105
• 1 ≤ U, V ≤ N
• 1 ≤ C, K ≤ 109
子任务 1（10 分）：
• 1 ≤ N, M ≤ 10
子任务 2（20 分）：
• 1 ≤ N, M ≤ 103
子任务 3（70 分）：
• 无附加限制
样例数据
输入
1
5
1 2 1
2 3 2
2 4 5
3 5 10
1
July Challenge 2017
6
5 4 5
5 4 10
5 4 1
1 2 1
4 1 10
1 5 8
输出
7
13
0
1
4
3

树剖裸题

//下次遇到这种小于等于k的题，可以考虑转离线然后一个指针暴扫加入。 
%:pragma GCC optimize(3)
using namespace std;
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define forw(i,x) for(int i=fir[x];i;i=ne[i])
#define lowbit(x) (x&(-x))
#define N 1000001
#define  getmid int mid=(L[no]+R[no])>>1;
#define lc no<<1
#define rc no<<1|1
#define pu(no) S[no]=S[lc]^S[rc]
int L[N],R[N],S[N];
//for segment tree
void build(int l,int r,int no)
{L[no]=l;R[no]=r;if(l==r){S[no]=0;return;}getmid;build(l,mid,lc);build(mid+1,r,rc);pu(no);
}
void chg(int no,int v,int x)
{if(L[no]==R[no]){S[no]=v;return;}getmid;if(x>mid) chg(rc,v,x);else chg(lc,v,x);pu(no);
}
int query(int no,int l,int r)
{if(L[no]==l&&R[no]==r) {return S[no];}getmid;if(l>r) return 0;if(l>mid) return query(rc,l,r);if(r<=mid) return query(lc,l,r);return query(lc,l,mid)^query(rc,mid+1,r);
}
struct edge{int id,C,from,to;
}xx[N];
bool cmp(edge a,edge b)
{return a.C<b.C;
}
int fir[N],ne[N],to[N];
int opt;
int n,m,tot,cnt;
int id[N],top[N];
int fa[N],gs[N];
int x,y,z;
int de[N],ans[N];
void add(int x,int y,int z)
{ne[++cnt]=fir[x];fir[x]=cnt;to[cnt]=y;
}
void ADD(int x,int y,int z)
{add(x,y,z);add(y,x,z);xx[++opt].C=z;xx[opt].from=x;xx[opt].to=y;
}
struct Query{int u,v,k,id;
}Q[N];
bool c(Query x,Query y)
{return x.k<y.k;
}
void dfs(int x,int f)
{de[x]=de[f]+1;fa[x]=f;S[x]=1;int tt=-1;gs[x]=0;forw(i,x){int V=to[i];if(V==f) continue;dfs(V,x);S[x]+=S[V];if(S[V]>tt){tt=S[V];gs[x]=V;}}return;
}
void getpos(int x,int sp)
{id[x]=++tot;top[x]=sp;if(gs[x]==0) return;getpos(gs[x],sp);forw(i,x){int V=to[i];if(V!=fa[x]&&V!=gs[x]){getpos(V,V);}}
}
int query_sum(int u,int v)
{int f1=top[u],f2=top[v];int ans=0;while(f1!=f2){if(de[f1]<de[f2]){swap(f1,f2);swap(u,v);}ans^=query(1,id[f1],id[u]);//坑点，下次要注意 u=fa[f1];f1=top[u];}if(de[u]<de[v]){swap(f1,f2);swap(u,v);}return ans^=query(1,id[v]+1,id[u]);
}
void init()
{memset(fir,0,sizeof(fir));cnt=0;tot=0;opt=0;scanf("%d",&n);for(int i=1;i<=n-1;i++){scanf("%d%d%d",&x,&y,&z);ADD(x,y,z);}sort(xx+1,xx+opt+1,cmp);    
}
void prework()
{dfs(1,0);getpos(1,1);build(1,tot,1); 
}
void doit()
{dfs(1,0);getpos(1,1);build(1,tot,1);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&Q[i].u,&Q[i].v,&Q[i].k);Q[i].id=i;}sort(Q+1,Q+m+1,c);int p=1;for(int i=1;i<=m;i++){for(;xx[p].C<=Q[i].k&&p<=opt;p++){if(fa[xx[p].from]==xx[p].to)chg(1,xx[p].C,id[xx[p].from]);else chg(1,xx[p].C,id[xx[p].to]);}ans[Q[i].id]=query_sum(Q[i].u,Q[i].v);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
int main()
{int t;scanf("%d",&t);while(t--) doit();
}