QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69653 | #5148. Tree Distance | myee | WA | 2075ms | 168488kb | C++11 | 4.2kb | 2022-12-29 15:32:14 | 2022-12-29 15:32:15 |
Judging History
answer
// 那就是希望。
// 即便需要取模,也是光明。
// lxl 题是吧。
// 叫 TEST_164,一看就是机械化大生产的产物。
// 根号做法似乎过不去,考虑 polylog 做法。
// 点分治,算出每个元素的深度,显然即求出区间内最小、次小值之和。
// 这样可以正确统计不同子树的信息,也不会因为子树内部信息干扰答案。
// 问题是这样每个询问都要 O(n\log n),肯定不行。
// 考虑怎么办。
// 怎样的信息可能被考虑?
// 考虑对右端点 r 做扫描线,然后考虑怎样的节点可能被考虑。
// 容易发现,维护一个单调栈,只有每个时刻可能相邻的元素才会被计入答案。
// 把这些信息全部记录下来,不会超过 O(n\log n) 个。
// 直接线段树维护,离线扫描即可。
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
std::vector<std::pair<uint,ullt> >Way[200005],D;
bol Gone[200005];
uint getsiz(uint p,uint f){
uint ans=1;
for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)ans+=getsiz(s.first,p);
return ans;
}
uint getwp(uint p,uint f,uint siz,uint&w,uint&wp){
uint ans=1,t=0,user;
for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)ans+=user=getwp(s.first,p,siz,w,wp),_max(t,user);
_max(t,siz-ans);if(_min(w,t))wp=p;
return ans;
}
voi get(uint p,uint f,ullt dep){
D.push_back({p,dep});
for(auto s:Way[p])if(!Gone[s.first]&&s.first!=f)get(s.first,p,dep+s.second);
}
std::vector<std::pair<uint,ullt> >Get[200005];
voi dfs(uint p){
{uint n=getsiz(p,-1);getwp(p,-1,n,n,p);}
D.clear(),get(p,-1,0),std::sort(D.begin(),D.end());
std::vector<std::pair<ullt,uint> >Stack;
for(auto s:D)
{
while(Stack.size()&&Stack.back().second>=s.second)
Get[s.first].push_back({Stack.back().first,Stack.back().second+s.second}),Stack.pop_back();
if(Stack.size())
Get[s.first].push_back({Stack.back().first,Stack.back().second+s.second});
Stack.push_back(s);
}
Gone[p]=1;for(auto s:Way[p])if(!Gone[s.first])dfs(s.first);
}
std::vector<uint>Q[200005];
uint L[1000005],R[1000005];
ullt Ans[1000005];
struct Seg{
Seg*L,*R;uint len;ullt v;
Seg(uint n):L(NULL),R(NULL),len(n),v(-1llu){if(n>1)L=new Seg(n>>1),R=new Seg(n-(n>>1));}
voi chg(uint p,ullt w){
_min(v,w);if(len==1)return;
p<(len>>1)?L->chg(p,w):R->chg(p-(len>>1),w);
}
ullt find(uint l,uint r){
if(!l&&r==len)return v;
if(l<(len>>1))
if(r<=(len>>1))return L->find(l,r);
else return std::min(L->find(l,len>>1),R->find(0,r-(len>>1)));
else return R->find(l-(len>>1),r-(len>>1));
}
};
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n,q;scanf("%u",&n);
for(uint i=1,u,v,w;i<n;i++)
scanf("%u%u%u",&u,&v,&w),
Way[--u].push_back({--v,w}),
Way[v].push_back({u,w});
scanf("%u",&q);
for(uint i=0;i<q;i++)
scanf("%u%u",L+i,R+i),L[i]--,Q[R[i]-1].push_back(i);
dfs(0);
Seg S(n);
for(uint i=0;i<n;i++){
for(auto s:Get[i])S.chg(s.first,s.second);
for(auto s:Q[i])Ans[s]=S.find(L[s],i+1);
}
for(uint i=0;i<q;i++)
printf("%lld\n",(llt)Ans[i]);
return 0;
}
// 那就是希望。
// 即便需要取模,也是光明。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 22556kb
input:
5 1 2 5 1 3 3 1 4 4 3 5 2 5 1 1 1 4 2 4 3 4 2 5
output:
-1 3 7 7 2
result:
ok 5 number(s): "-1 3 7 7 2"
Test #2:
score: -100
Wrong Answer
time: 2075ms
memory: 168488kb
input:
199999 31581 23211 322548833 176307 196803 690953895 34430 82902 340232856 36716 77480 466375266 7512 88480 197594480 95680 61864 679567992 19572 14126 599247796 188006 110716 817477802 160165 184035 722372640 23173 188594 490365246 54801 56250 304741654 10103 45884 643490340 127469 154479 214399361...
output:
7975953 838538161068 1262 65959 4366 2623368956 158116029 4867978 328055210 4654349801 506443262 339719 76251 76251 4366 138216269 875595 2826267332 2681285 4366 189703 69287 65959 196947420 92126 15146 4072081890 24465023 5718199 189703 92126 1162886184 92195705 92126 189703 76251 189703 4366 -1 -1...
result:
wrong answer 1st numbers differ - expected: '29573323', found: '7975953'