本文共 3799 字，大约阅读时间需要 12 分钟。
There are some queries on a tree which has n nodes. Every query is described as two integers (X, Y).For each query, you should find the maximum weight of the edges in set E, which satisfies the following two conditions.
- The edge must on the path from node X to node 1.
- The edge’s weight should be lower or equal to Y. Now give you the tree and queries. Can you find out the answer for each query? Input The first line of the input is an integer T, indicating the number of test cases. For each case, the first line contains an integer n indicates the number of nodes in the tree. Then n-1 lines follows, each line contains three integers X, Y, W indicate an edge between node X and node Y whose value is W. Then one line has one integer Q indicates the number of queries. In the next Q lines, each line contains two integers X and Y as said above. Output For each test case, you should output Q lines. If no edge satisfy the conditions described above，just output “-1” for this query. Otherwise output the answer for this query. Sample Input 1 3 1 2 7 2 3 5 4 3 10 3 7 3 6 3 4 Sample Output 7 7 5 -1
Hint
2<=n<=10^5
2<=Q<=10^5
1<=W,Y<=10^9
The data is guaranteed that your program will overflow if you use recursion.
给你一个树,树上的每条边都有一个边权.
有m个询问,每次都询问结点1到结点x经过的边上,边权小于等于k最大的是多少.
很明显的树链剖分…但是怎么每次都去找到这个最符合的权值.
还有一点,这给的是边权,要是用线段树维护的话,至少应该是点权.这个怎么弄???
这里我们应该将边权转换为点权…一般是转换为深度大的点的点权…这样我们在以后更新时,就不会漏掉某一个边权…而且这样一弄就成了区间去最大值了…
这个题应该是离线处理,先把所有的都存起来.由小到大排序后,在依次离线处理…结合上面的操作
代码如下:
#include #include #include #include #include #include #include #include #define ll long longusing namespace std;const int maxx=1e5+100;const int inf=0x3f3f3f3f;struct edge{ int to; int next;}e[maxx<<1];struct node{ int l; int r; int v; }p[maxx<<2];struct Node{ int x; int y; int v; bool operator<(const Node &a)const { return a.v>v; } }a1[maxx];struct Node1{ int x; int y; int id; bool operator<(const Node1 &a)const { return a.y>y; }}a2[maxx];int head[maxx<<1],dep[maxx],size[maxx],top[maxx];int pre[maxx],s[maxx],fa[maxx],son[maxx],ans[maxx];int tot,n,m,sign;/*-----------------事前准备-------------*/ void init(){ tot=sign=0; memset(head,-1,sizeof(head)); memset(son,0,sizeof(son)); }void add(int u,int v){ e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}/*-------------------dfs-----------------*/void dfs1(int u,int f){ dep[u]=dep[f]+1; size[u]=1; fa[u]=f; for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==f) continue; dfs1(to,u); size[u]+=size[to]; if(size[to]>size[son[u]]) son[u]=to; }}void dfs2(int u,int Top){ top[u]=Top; s[u]=++sign; pre[sign]=u; if(son[u]) dfs2(son[u],Top); for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==son[u]||to==fa[u]) continue; dfs2(to,to); }}/*-----------------线段树------------------*/ void pushup(int cur){ p[cur].v=max(p[cur<<1].v,p[cur<<1|1].v);}void build(int l,int r,int cur){ p[cur].l=l; p[cur].r=r; if(l==r) { p[cur].v=-inf; return ; } int mid=(l+r)>>1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1); pushup(cur);}void update(int x,int cur,int add){ int L=p[cur].l; int R=p[cur].r; if(L==R) { p[cur].v=add; return ; } int mid=(L+R)>>1; if(x<=mid) update(x,cur<<1,add); else update(x,cur<<1|1,add); pushup(cur);}int query(int l,int r,int cur){ int L=p[cur].l; int R=p[cur].r; if(l<=L&&R<=r) { return p[cur].v; } int mid=(L+R)>>1; if(r<=mid) return query(l,r,cur<<1); else if(l>mid) return query(l,r,cur<<1|1); else return max(query(l,mid,cur<<1),query(mid+1,r,cur<<1|1));}/*---------------树链剖分----------------*/int solve(int x,int y){ int ans=-1; while(top[x]!=top[y]) { if(dep[top[x]] s[y]) swap(x,y); ans=max(ans,query(s[x],s[y],1)); return ans;} int main(){ int dd; scanf("%d",&dd); while(dd--) { init(); scanf("%d",&n); for(int i=1;i a2[i].y) break; if(dep[a1[j].x]
努力加油a啊,(o)/~
转载地址：http://kfxvi.baihongyu.com/